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]
anddictionary[j]
are composed of lowercase English letters.
Solution: Hamming distance + Brute Force
For each query word q, check the hamming distance between it and all words in the dictionary.
Time complexity: O(|q|*|d|*n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) { const int n = queries[0].size(); auto check = [&](string_view q) { for (const string& w : dictionary) { int dist = 0; for (int i = 0; i < n && dist <= 3; ++i) dist += q[i] != w[i]; if (dist <= 2) return true; } return false; }; vector<string> ans; for (const string& q : queries) if (check(q)) ans.push_back(q); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment