你有一个单词列表 words 和一个模式 pattern,你想知道 words 中的哪些单词与模式匹配。
如果存在字母的排列 p ,使得将模式中的每个字母 x 替换为 p(x) 之后,我们就得到了所需的单词,那么单词与模式是匹配的。
(回想一下,字母的排列是从字母到字母的双射:每个字母映射到另一个字母,没有两个字母映射到同一个字母。)
返回 words 中与给定模式匹配的单词列表。
你可以按任何顺序返回答案。
var findAndReplacePattern = function(words, pattern) { // Map 实现
const r = []
label: for (let i = 0; i < words.length; i++) {
const wMap = new Map, pMap = new Map
const word = words[i]
for (let j = 0; j < pattern.length; j++) {
const w = word[j], p = pattern[j]
if (pMap.has(p) == false && wMap.has(w) == false) {
pMap.set(p, w)
wMap.set(w, p)
} else if (pMap.get(p) !== w || wMap.get(w) !== p) continue label
}
r.push(word)
}
return r
};
var findAndReplacePattern = function(words, pattern) { // Objcect 实现
const r = []
label: for (let i = 0; i < words.length; i++) {
const wMap = Object.create(null), pMap = Object.create(null)
const word = words[i]
for (let j = 0; j < pattern.length; j++) {
const w = word[j], p = pattern[j]
if (pMap[p] === void 0 && wMap[w] === void 0) {
pMap[p] = w
wMap[w] = p
} else if (pMap[p] !== w || wMap[w] !== p) continue label
}
r.push(word)
}
return r
};
var findAndReplacePattern = function(words, pattern) { // Uint8Array 同构数组实现
const r = []
label: for (let i = 0; i < words.length; i++) {
const wMap = new Uint8Array(27), pMap = new Uint8Array(27)
const word = words[i]
for (let j = 0; j < pattern.length; j++) {
const w = word.charCodeAt(j) - 96, p = pattern.charCodeAt(j) - 96
if (pMap[p] === 0 && wMap[w] === 0) {
pMap[p] = w
wMap[w] = p
} else if (pMap[p] !== w || wMap[w] !== p) continue label
}
r.push(word)
}
return r
};
function findAndReplacePattern(words: string[], pattern: string): string[] {
const r: string[] = []
label: for (let i = 0; i < words.length; i++) {
const wMap = new Uint8Array(27), pMap = new Uint8Array(27)
const word = words[i]
for (let j = 0; j < pattern.length; j++) {
const w = word.charCodeAt(j) - 96, p = pattern.charCodeAt(j) - 96
if (wMap[w] === 0 && pMap[p] === 0) {
wMap[w] = p
pMap[p] = w
} else if (wMap[w] !== p || pMap[p] !== w) continue label
}
r.push(word)
}
return r
};
class Solution {
public List<String> findAndReplacePattern(String[] words, String pattern) { // HashMap 实现
List<String> r = new ArrayList<String>();
label: for (String word: words) {
HashMap<Character, Character> pMap = new HashMap<Character, Character>();
HashMap<Character, Character> wMap = new HashMap<Character, Character>();
int n = pattern.length();
for (int i = 0; i < n; i++) {
char p = pattern.charAt(i), w = word.charAt(i);
if (pMap.containsKey(p) == false && wMap.containsKey(w) == false) {
pMap.put(p, w);
wMap.put(w, p);
} else if (pMap.containsKey(p) && pMap.get(p) != w || wMap.containsKey(w) && wMap.get(w) != p) continue label;
}
r.add(word);
}
return r;
}
}
class Solution {
public List<String> findAndReplacePattern(String[] words, String pattern) { // int[] 实现
List<String> r = new ArrayList<String>();
label: for (String word: words) {
int[] pMap = new int[27];
int[] wMap = new int[27];
int n = pattern.length();
for (int i = 0; i < n; i++) {
int p = pattern.charAt(i) - 96, w = word.charAt(i) - 96;
if (pMap[p] == 0 && wMap[w] == 0) {
pMap[p] = w;
wMap[w] = p;
} else if (pMap[p] != w || wMap[w] != p) continue label;
}
r.add(word);
}
return r;
}
}
func findAndReplacePattern(words []string, pattern string) []string { // []int 实现
var r []string
label: for _, word := range words {
pMap, wMap := make([]int, 27), make([]int, 27)
for i, _ := range pattern {
p, w := int(pattern[i]) - 96, int(word[i]) - 96
if pMap[p] == 0 && wMap[w] == 0 {
pMap[p] = w
wMap[w] = p
} else if pMap[p] != w || wMap[w] != p {
continue label
}
}
r = append(r, word)
}
return r
}
func findAndReplacePattern(words []string, pattern string) []string { // []byte 实现
var r []string
label: for _, word := range words {
pMap, wMap := make([]byte, 27), make([]byte, 27)
for i, _ := range pattern {
p, w := pattern[i] - 96, word[i] - 96
if pMap[p] == 0 && wMap[w] == 0 {
pMap[p] = w
wMap[w] = p
} else if pMap[p] != w || wMap[w] != p {
continue label
}
}
r = append(r, word)
}
return r
}
class Solution:
def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]: # Dict 实现
r = []
for word in words:
pMap, wMap, isVaild = {}, {}, True
for i, p in enumerate(pattern):
w, p = word[i], pattern[i]
if p not in pMap and w not in wMap:
pMap[p] = w
wMap[w] = p
elif p in pMap and pMap[p] != w or w in wMap and wMap[w] != p:
isVaild = False
break
if isVaild: r.append(word)
return r
class Solution:
def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]: # Dict + filter 实现
def match(word: List[str]) -> bool:
wMap, pMap = {}, {}
for w, p in zip(word, pattern):
if w not in wMap: wMap[w] = p
if p not in pMap: pMap[p] = w
if (wMap[w], pMap[p]) != (p, w): return False
return True
return list(filter(match, words))
class Solution {
function findAndReplacePattern($words, $pattern) {
$r = array();
foreach($words as $word) {
$pMap = array_fill(0, 27, 0);
$wMap = array_fill(0, 27, 0);
for ($i = 0; $i < strlen($pattern); $i++) {
$w = ord($word[$i]) - 96;
$p = ord($pattern[$i]) - 96;
if ($pMap[$p] === 0) $pMap[$p] = $w;
if ($wMap[$w] === 0) $wMap[$w] = $p;
if ($pMap[$p] !== $w || $wMap[$w] !== $p) continue 2;
}
$r []= $word;
}
return $r;
}
}