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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
| package airbnb;
import java.util.LinkedList; import java.util.List; import java.util.Queue;
public class KEditDistance {
public static void main(String[] args) { KEditDistance kEditDistance = new KEditDistance(); TrieNode root = kEditDistance.new TrieNode(); String[] lists = new String[] {"abcd", "abc", "abd","ad"}; String word = "ac"; int k = 1; List<String> result = kEditDistance.getKEditDistance(lists, word, k, root); for (String s : result) { System.out.println(s); } } public List<String> getKEditDistance(String[] lists, String target, int k, TrieNode root) { List<String> result = new LinkedList<>(); if (lists == null || lists.length == 0 || target == null || target.length() == 0 || k < 0) { return result; } for (String s : lists) { root.add(s); } int[] prevDist = new int[target.length() + 1]; for (int i = 0; i < prevDist.length; i++) { prevDist[i] = i; } computeDistance("", prevDist, target, k, root, result); return result; } public void computeDistance(String cur, int[] prevDist, String target, int k, TrieNode node, List<String> result) { if (node.isWord) { if (prevDist[target.length()] <= k) { result.add(cur); } else { return; } }
for (int i = 0; i < 26; i++) { if (node.children[i] == null) { continue; }
int[] curDist = new int[target.length() + 1]; curDist[0] = cur.length() + 1; for (int j = 1; j < prevDist.length; j++) { if (target.charAt(j - 1) == (char) (i + 'a')) { curDist[j] = prevDist[j - 1]; } else { curDist[j] = Math.min(Math.min(prevDist[j - 1], prevDist[j]), curDist[j - 1]) + 1; } } computeDistance(cur + (char)(i + 'a'), curDist, target, k, node.children[i], result); } } public void print(TrieNode root) { TrieNode cur = root; int level = 0; Queue<TrieNode> queue = new LinkedList<>(); queue.add(cur); while (!queue.isEmpty()) { int size = queue.size(); while (size > 0) { cur = queue.poll(); System.out.println("level " + level + cur.character); for (int i = 0; i < cur.children.length; i++) { if (cur.children[i] != null) { queue.add(cur.children[i]); } } size--; } level++; } } class TrieNode { boolean isWord; TrieNode[] children; char character; public TrieNode() { children = new TrieNode[26]; } public void add(String s) { if (s == null || s.length() == 0) { return; } TrieNode cur = this; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (cur.children[c - 'a'] == null) { cur.children[c - 'a'] = new TrieNode(); } cur = cur.children[c - 'a']; cur.character = c; } cur.isWord = true; } }
}
|