Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/890.html
890. Find and Replace Pattern (Medium)
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 <= 501 <= pattern.length = words[i].length <= 20
Related Topics:
String
Solution 1.
// OJ: https://leetcode.com/problems/find-and-replace-pattern/
// Time: O(CW) where C is count of words and W is word length
// Space: O(W)
class Solution {
private:
bool match(string &word, string &pattern) {
unordered_map<char, char> m;
unordered_set<char> used;
for (int i = 0; i < word.size(); ++i) {
if (m.find(word[i]) == m.end()) {
if (used.find(pattern[i]) != used.end()) return false;
m[word[i]] = pattern[i];
used.insert(pattern[i]);
} else if (m[word[i]] != pattern[i]) return false;
}
return true;
}
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string> ans;
for (auto word : words) {
if (match(word, pattern)) ans.push_back(word);
}
return ans;
}
};
-
class Solution { public List<String> findAndReplacePattern(String[] words, String pattern) { List<String> matchWords = new ArrayList<String>(); for (String word : words) { if (matchPattern(word, pattern)) matchWords.add(word); } return matchWords; } public boolean matchPattern(String word, String pattern) { if (word.length() != pattern.length()) return false; Map<Character, Character> map1 = new HashMap<Character, Character>(); Map<Character, Character> map2 = new HashMap<Character, Character>(); int length = word.length(); for (int i = 0; i < length; i++) { char c1 = word.charAt(i), c2 = pattern.charAt(i); if (map1.containsKey(c1)) { if (map1.get(c1) != c2) return false; } else map1.put(c1, c2); if (map2.containsKey(c2)) { if (map2.get(c2) != c1) return false; } else map2.put(c2, c1); } return true; } } ############ class Solution { public List<String> findAndReplacePattern(String[] words, String pattern) { List<String> ans = new ArrayList<>(); for (String word : words) { if (match(word, pattern)) { ans.add(word); } } return ans; } private boolean match(String s, String t) { int[] m1 = new int[128]; int[] m2 = new int[128]; for (int i = 0; i < s.length(); ++i) { char c1 = s.charAt(i); char c2 = t.charAt(i); if (m1[c1] != m2[c2]) { return false; } m1[c1] = i + 1; m2[c2] = i + 1; } return true; } } -
// OJ: https://leetcode.com/problems/find-and-replace-pattern/ // Time: O(CW) where C is count of words and W is word length // Space: O(W) class Solution { private: bool match(string &word, string &pattern) { unordered_map<char, char> m; unordered_set<char> used; for (int i = 0; i < word.size(); ++i) { if (m.find(word[i]) == m.end()) { if (used.find(pattern[i]) != used.end()) return false; m[word[i]] = pattern[i]; used.insert(pattern[i]); } else if (m[word[i]] != pattern[i]) return false; } return true; } public: vector<string> findAndReplacePattern(vector<string>& words, string pattern) { vector<string> ans; for (auto word : words) { if (match(word, pattern)) ans.push_back(word); } return ans; } }; -
class Solution: def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]: def match(s, t): m1, m2 = [0] * 128, [0] * 128 for i, (a, b) in enumerate(zip(s, t), 1): if m1[ord(a)] != m2[ord(b)]: return False m1[ord(a)] = m2[ord(b)] = i return True return [word for word in words if match(word, pattern)] ############ class Solution(object): def findAndReplacePattern(self, words, pattern): """ :type words: List[str] :type pattern: str :rtype: List[str] """ ans = [] set_p = set(pattern) for word in words: if len(set(word)) != len(set_p): continue fx = dict() equal = True for i, w in enumerate(word): if w in fx: if fx[w] != pattern[i]: equal = False break fx[w] = pattern[i] if equal: ans.append(word) return ans -
func findAndReplacePattern(words []string, pattern string) []string { match := func(s, t string) bool { m1, m2 := make([]int, 128), make([]int, 128) for i := 0; i < len(s); i++ { if m1[s[i]] != m2[t[i]] { return false } m1[s[i]] = i + 1 m2[t[i]] = i + 1 } return true } var ans []string for _, word := range words { if match(word, pattern) { ans = append(ans, word) } } return ans } -
function findAndReplacePattern(words: string[], pattern: string): string[] { return words.filter(word => { const map1 = new Map<string, number>(); const map2 = new Map<string, number>(); for (let i = 0; i < word.length; i++) { if (map1.get(word[i]) !== map2.get(pattern[i])) { return false; } map1.set(word[i], i); map2.set(pattern[i], i); } return true; }); } -
use std::collections::HashMap; impl Solution { pub fn find_and_replace_pattern(words: Vec<String>, pattern: String) -> Vec<String> { let pattern = pattern.as_bytes(); let n = pattern.len(); words .into_iter() .filter(|word| { let word = word.as_bytes(); let mut map1 = HashMap::new(); let mut map2 = HashMap::new(); for i in 0..n { if map1.get(&word[i]).unwrap_or(&n) != map2.get(&pattern[i]).unwrap_or(&n) { return false; } map1.insert(word[i], i); map2.insert(pattern[i], i); } true }) .collect() } }