336. Palindrome Pairs - cocoder39/coco39_LC GitHub Wiki

336. Palindrome Pairs

Notes 2021:

case 1 is a special case of case 2 or case 3 where the palindrome is empty. However, attempting to handle case 1 in case2 or case 3 will complicate the logic. It is clear to handle them separately.

Time complexity suppose avg len of word is k and len(words) = n

  • O(n) to insert to dict
  • case 1: O(n * k)
  • case 2: O(k^2) to get prefix list for each word so O(n*k^2) in total
  • case 3: same as case 2
  • T = O(n * k^2)

Space complexity:

  • O(n*k) to create dict
  • case 1: O(k) to create reverseWord in each loop
  • case 2: Prefix list can contain at most k words where each word of length 1, 2, ... k so total is O(k^2)
  • case 3: same as case 2
  • input: O(n*k)
  • output: O(n^2) total = O(nk + k^2 + k^2 + nk + n^2)
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        wordDict = {word: i for i, word in enumerate(words)}
        res = []
        for i, word in enumerate(words):
            reverseWord = word[::-1]
            if reverseWord in wordDict and i != wordDict[reverseWord]:
                res.append([i, wordDict[reverseWord]])
                
            for prefix in self.getAllValidPrefix(word):
                reversePrefix = prefix[::-1]
                if reversePrefix in wordDict:
                    res.append([i, wordDict[reversePrefix]])
                    
            for suffix in self.getAllValidSuffix(word):
                reverseSuffix = suffix[::-1]
                if reverseSuffix in wordDict:
                    res.append([wordDict[reverseSuffix], i])
        
        return res           
    
    # word = palindrome prefix + valid suffix
    def getAllValidSuffix(self, word) -> List[str]:
        res = []
        for i in range(len(word)):
            if word[:i+1] == word[:i+1][::-1]: 
                res.append(word[i+1:])
        return res

    # word = valid prefix + palindrome suffix
    def getAllValidPrefix(self, word) -> List[str]:
        res = []
        for i in range(len(word)):
            if word[i:] == word[i::][::-1]:
                res.append(word[:i])
        return res

================================================================================

main idea:

  • check all the other string whose length is no more than words[i].length()

equal length: check if there exists a string that is the reverse of words[i]

shorter length: check if the words[i] can concatenate a shorter string to generate palindrome.

  • use set to speed up length searching

time complexity is O(len * n^2) where len is length of a word and n is size of words

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        unordered_map<string, int> map;
        set<int> lens;
        for (int i = 0; i < words.size(); i++) {
            map[words[i]] = i; //given unique words
            lens.insert(words[i].length());
        }
        
        for (int i = 0; i < words.size(); i++) {
            string r = words[i];
            int len = r.length();
            reverse(r.begin(), r.end());
            if (map.find(r) != map.end() && map[r] != i) // in case of t itself is a palindreme
                res.push_back({i, map[r]}); //eg. map[r] = tab, words[i] = bat
            
            auto it = lens.find(len);
            for (auto it1 = lens.begin(); it1 != it; it1++) {
                int l = *it1;
                if (isValid(r, 0, len - l - 1) && map.find(r.substr(len - l)) != map.end()) //right part of words[i] is a palindrome
                    res.push_back({i, map[r.substr(len - l)]});
                if (isValid(r, l, len - 1) && map.find(r.substr(0, l)) != map.end()) //left part of words[i] is a palindrome
                    res.push_back({map[r.substr(0, l)], i});
            }
        }
        return res;
    }
private:
    bool isValid(string s, int left, int right) {
        while (left < right)
            if (s[left++] != s[right--])    return false;
        return true;
    }
};
⚠️ **GitHub.com Fallback** ⚠️