Lintcode 623. K Edit Distance

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 than k.

You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example

Given words = ["abc", "abd", "abcd", "adc"] and target = "ac", k = 1
Return ["abc", "adc"]




Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

public class Solution {     /**      * @param words: a set of stirngs      * @param target: a target string      * @param k: An integer      * @return: output all the strings that meet the requirements      */     public List<String> kDistance(String[] words, String target, int k) {         List<String> ans = new ArrayList<>();         if (words == null || words.length == 0 || k < 0) {             return ans;         }                   Trie trie = new Trie();         for (String word : words) {             trie.insert(word);         }                   TrieNode p = trie.root;                   int[] dp = new int[target.length() + 1];         for (int i = 0; i < dp.length; i++) {             dp[i] = i;         }                   kDistanceHelper(p, dp, target, k, ans);                   return ans;     }           private void kDistanceHelper(TrieNode p, int[] dp, String target, int k, List<String> ans) {         if (p == null) {             return;         }                   if (p.leaf && dp[target.length()] <= k) {             ans.add(p.word);         }                   int[] curr = new int[target.length() + 1];         curr[0] = dp[0] + 1;                   for (char c = 'a'; c <= 'z'; c++) {             if (p.children[c - 'a'] != null) {                 for (int j = 1; j <= target.length(); j++) {                     if (c == target.charAt(j - 1)) {                         curr[j] = dp[j - 1];                     } else {                         curr[j] = Math.min(dp[j - 1], Math.min(dp[j], curr[j - 1])) + 1;                     }                 }                 kDistanceHelper(p.children[c - 'a'], curr, target, k, ans);             }         }     } }   class Trie {     TrieNode root;     public Trie() {         root = new TrieNode();     }           public void insert(String word) {         TrieNode p = root;         for (char c : word.toCharArray()) {             if (p.children[c - 'a'] == null) {                 p.children[c - 'a'] = new TrieNode();             }             p = p.children[c - 'a'];         }                   p.leaf = true;         p.word = word;     } }   class TrieNode {     TrieNode[] children;     boolean leaf;     String word;           public TrieNode() {         children = new TrieNode[26];         leaf = false;         word = "";     } }