leetcode-algorithms/src/CountPrefixAndSuffixPairsI.java at master · anishLearnsToCode/leetcode-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// https://leetcode.com/problems/count-prefix-and-suffix-pairs-i
// T: O(|words|^2 * |words[i].length|)
// S: O(1)

public class CountPrefixAndSuffixPairsI {
    public int countPrefixSuffixPairs(String[] words) {
        int pairs = 0;
        for (int i = 0 ; i < words.length ; i++) {
            for (int j = i + 1 ; j < words.length ; j++) {
                if (isPrefixAndSuffix(words[i], words[j])) {
                    pairs++;
                }
            }
        }
        return pairs;
    }

    private static boolean isPrefixAndSuffix(String a, String b) {
        if (a.length() > b.length()) {
            return false;
        }

        // prefix
        for (int i = 0 ; i < a.length() ; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                return false;
            }
        }

        //suffix
        for (int i = 0; i < a.length() ; i++) {
            if (a.charAt(i) != b.charAt(b.length() - a.length() + i)) {
                return false;
            }
        }

        return true;
    }
}