You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length.
In one edit you can take a word from queries, and change any letter in it to any other letter. Find all words from queries that, after a maximum of two edits, equal some word from dictionary.
Return a list of all words from queries, that match with some word from dictionary after a maximum of two edits. Return the words in the same order they appear in queries.
Example 1:
Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output:
["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
Thus, we return ["word","note","wood"].
Example 2:
Input: queries = ["yes"], dictionary = ["not"]
Output:
[]
Explanation:
Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.
Constraints:
1 <= queries.length, dictionary.length <= 100
n == queries[i].length == dictionary[j].length
1 <= n <= 100
All queries[i] and dictionary[j] are composed of lowercase English letters.
解題
使用暴力解來算 漢明距離 是否小於 3 ，若是的話加入回傳的陣列
Runtime: 0 ms, faster than 100%
Memory Usage: 3.2 MB, less than 87.50%
func twoEditWords(queries []string, dictionary []string) []string {
res := make([]string, 0)
for _, str := range queries {
for _, word := range dictionary {
if len(str) != len(word) {
continue
}
if hammingDistanceLessThanTwo(str, word) {
res = append(res, str)
break
}
}
}
return res
}
func hammingDistanceLessThanTwo(a, b string) bool {
diff := 0
for i:=0; i<len(a); i++ {
if a[i] != b[i] {
diff++
}
if diff > 2 {
return false
}
}
return true
}