Given a set of strings which just has lower case letters and a target string, output all the strings for each the edit distance with the target no greater thank.
You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Have you met this question in a real interview?
Yes
Example
Given words =["abc", "abd", "abcd", "adc"]and target ="ac", k =1
Return["abc", "adc"]
put TrieNode class before solution
line 23 missing setting the str.
line 65 trick subtract 'a'
line 63 pay attention
line 68 condition don't forget dp[j - 1] + 1 case
class TrieNode {
public:
TrieNode\(\) {
for \(int i = 0; i < 26; ++i\) {
child\[i\] = NULL;
}
isWord = false;
}
bool isWord;
string str;
TrieNode\* child\[26\];
static void InsertWord\(TrieNode\* root, const string& word\) {
TrieNode\* p = root;
for \(char ch : word\) {
if \(p->child\[ch - 'a'\] == NULL\) {
p->child\[ch - 'a'\] = new TrieNode\(\);
}
p = p->child\[ch - 'a'\];
}
p->isWord = true;
p->str = word;
}
};
class Solution {
public:
/\*\*
\* @param words a set of stirngs
\* @param target a target string
\* @param k an integer
\* @return output all the strings that meet the requirements
\*/
vector<string> kDistance\(vector<string>& words, string& target, int k\) {
// Write your code here
vector<string> res;
TrieNode\* root = new TrieNode\(\);
for \(string& word : words\) {
TrieNode::InsertWord\(root, word\);
}
int n = target.length\(\);
vector<int> dp\(n + 1\);
for \(int i = 0; i < dp.size\(\); ++i\) {
dp\[i\] = i;
}
find\(root, res, target, k, dp\);
return res;
}
void find\(TrieNode\* root, vector<string>& res, string& target, int k, vector<int>& dp\) {
int n = target.size\(\);
if \(root->isWord && dp\[n\] <= k\) {
res.push\_back\(root->str\);
}
vector<int> next\(n + 1, 0\);
for \(int i = 0; i < 26; ++i\) {
if \(root->child\[i\] == NULL\) {
continue;
}
next\[0\] = dp\[0\] + 1;
for \(int j = 1; j <= n; ++j\) {
if \(target\[j - 1\] - 'a' == i\) {
next\[j\] = dp\[j - 1\];
} else {
next\[j\] = min\(min\(dp\[j\], next\[j - 1\]\), dp\[j - 1\]\) + 1;
}
}
find\(root->child\[i\], res, target, k, next\);
}
}
};