Skip to content

← leetcode

Count Prefix and Suffix Pairs I

· Easy

LeetCode problem 3042

Maybe simplest solution is the best solution!?

I just brute-forced it; sorting the words array by words[i].size(), iterating through all pairs inside words and checking if words[i] is both a prefix and a suffix of words[j] for 0 <= i < j <= words.size() where words[i].size() <= words[j].size().

Potential improvements would be to use a trie and "reverse" trie to store the prefixes and suffixes respectively.

code

class Solution {
public:
    int countPrefixSuffixPairs(vector<string>& words) {
        int ans = 0;
        for (int i = 0 ; i < words.size(); ++i) {
            for (int j = i+1; j < words.size(); ++j) {
                if (words[i].size() > words[j].size()) continue;
                if (words[j].substr(0, words[i].size()) == words[i]
                    && words[j].substr(words[j].size()-words[i].size(), words[i].size()) == words[i]) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

ComplexityL

  • Time: O(n^2)
  • Space: O(1)