Problem
You have a list ofĀ words
Ā and aĀ pattern
, and you want to know which words inĀ words
Ā matches the pattern.
A word matches the pattern if there exists a permutation of lettersĀ p
Ā so that after replacing every letterĀ x
Ā in the pattern withĀ p(x)
, we get the desired word.
(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)
Return a list of the words inĀ words
Ā that match the given pattern.
You may return the answer in any order.
Example 1:
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb" Output: ["mee","aqq"] Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. "ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to the same letter.
Note:
1 <= words.length <= 50
1 <= pattern.length = words[i].lengthĀ <= 20
Solution: RememberĀ the last pos of each char.
Time complexity: O(n*l)
Space complexity: O(128) -> O(26)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 0 ms class Solution { public: vector<string> findAndReplacePattern(vector<string>& words, string pattern) { vector<string> ans; for (const string& w : words) if (match(w, pattern)) ans.push_back(w); return ans; } private: bool match(const string& w, const string& p) { vector<int> last_pos_w(128, INT_MIN); // last pos of x in w vector<int> last_pos_p(128, INT_MIN); // last pos of x in p for (int i = 0; i < w.size(); ++i) if (last_pos_w[w[i]] != last_pos_p[p[i]]) { return false; } else { last_pos_w[w[i]] = last_pos_p[p[i]] = i; } return true; } }; |