- Number of Matching Subsequences
- Longest Word in Dictionary through Deleting
这两道题一起来总结一下。
把它们放在一起，是因为他俩几乎是同一道题。
都是找一个单词是不是另外一个单词的subsequence.
如果只找一次的话，用双指针做一下就好了。
如果像792和524那样要找很多次，为了加速优化如下。
把母单词的letter统计一下，每个letter记下他出现的位置，记在一个List<Integer>里面。然后要有 26个这样的List<Integer>
对于子单词，用一个指针从左到右。假设第一个字母是b， 我就去找到母单词的b对应的List<Integer>找到他第一个出现的位置， 假设是 3， 我记下来。下一个字母假设是C， 我就去母单词c对应的List<Integer>里找c在3之后第一次出现的位置。这时可以用二分查找加速。
时间复杂度，我想了一下，就没在这里写了，需要做假设再讨论。
这题容易出错的点：
- List[] locations = new ArrayList[26]; 这是对的。
如果要建 Array of List, 请用这种形式。
List<Integer>[] locations = new ArrayList<Integer>[26]; 这是错的。
List<Integer>[] locations = new ArrayList<>[26]; 这也是错的
List<Integer>[] locations = new ArrayList[26]; 这也是对的
总之后面的ArrayList那里什么也不要多写。 - 这题在binarySearch的时候，有两个index的概念，一个是List<Integer>里面的index, 一个List<Integer>里面的value, 恰恰这个value也是index，是母单词字母的index， 非常容易搞混。特别特别小心。
代码
先贴524的。
public String findLongestWord(String s, List<String> d) {
String ans = "";
List[] counts = new ArrayList[26];
for (int i = 0; i < 26; i++) {
counts[i] = new ArrayList<>();
}
for (int i = 0; i < s.length(); i++) {
counts[s.charAt(i) - 'a'].add(i);
}
for (String w : d) {
if (w.length() < ans.length()) continue;
if (contains(counts, w)) {
if (w.length() > ans.length() || (w.compareTo(ans) < 0))
ans = w;
}
}
return ans;
}
private boolean contains(List[] counts, String w) {
int pt = -1;
for (char c : w.toCharArray()) {
pt = binarySearch(counts[c - 'a'], pt + 1);
if (pt == -1) return false;
}
return true;
}
private int binarySearch(List<Integer> list, int target) {
if (list.size() == 0 ) return -1;
int l = 0, r = list.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
int midVal = list.get(mid);
if (midVal == target) return midVal;
if (midVal < target) {
l = mid + 1;
} else {
r = mid;
}
}
if (list.get(l) >= target) return list.get(l);
return -1;
}
再贴 792的
public int numMatchingSubseq(String S, String[] words) {
List[] locations = new ArrayList[26];
for (int i = 0; i < 26; i++) {
locations[i] = new ArrayList<Integer>();
}
for (int i = 0; i < S.length(); i++) {
locations[S.charAt(i) - 'a'].add(i);
}
int count = 0;
for (String w : words) {
if (contains(locations, w)) count++;
}
return count;
}
private boolean contains(List[] locations, String w) {
int pt = -1;
for (char c : w.toCharArray()) {
pt = findNext(locations[c - 'a'], pt + 1);
if (pt == -1) return false;
}
return true;
}
private int findNext(List<Integer> indexes, int left) {
if (indexes.size() == 0) return -1;
int l = 0, r = indexes.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
int midPos = indexes.get(mid);
if (midPos == left) return left;
if (midPos < left) {
l = mid + 1;
} else {
r = mid;
}
}
if (indexes.get(r) >= left ) return indexes.get(r);
return -1;
}
