3042. Count Prefix and Suffix Pairs I

[Problem]

Array String Trie Rolling Hash String Matching Hash Function

---

Intuition

• Brute Force works because constraints are small.

Constraints:
1 <= words.length <= 50
1 <= words[i].length <= 10

Approach

• For each word, compare it with the remaining words (avoiding duplicate checks).
• Check if the first word (str1) is both a prefix and suffix of the second word (str2).

Complexity Analysis

• Time Complexity: O(n^2*k)
  • n: Number of words in the array.
  • k: Average length of the words (checking startsWith and endsWith takes O(k)).
• Space Complexity: O(1)
  • No extra space used.

Code

class Solution {
    public int countPrefixSuffixPairs(String[] words) {
        int wLen = words.length;
        int cnt = 0;
        
        // brute force all pairs
        for (int i = 0; i < wLen; i++) {
            String str1 = words[i];
            
            for (int j = i + 1; j < wLen; j++) {
                String str2 = words[j];

                // Ensure`str1` is smaller or equal in length
                if (str1.length() <= str2.length()) {
                    // Check if `str1` is both a prefix and suffix of `str2`
                    if (str2.startsWith(str1) && str2.endsWith(str1)) {
                        cnt++;
                    }
                }
            }
        }

        // total count of valid pairs
        return cnt;
    }
}