392. 判断子序列续（leetcode 解题）-热点指南

继续接着上一题，现在就是完成挑战了。

此时的s的数量过大，可以通过对长字符串t做预先处理以生成易于搜索的内容来提高效率。将t中含有的所有字母出现的下标存在map中，key：character 字符 value： List 所有出现的下标。

public boolean isSubsequence(String s, String t) {
 if (s == null || t == null) return false;

 Map> map = new HashMap<>(); //

 //处理t
 for (int i = 0; i < t.length(); i++) {
 char curr = t.charAt(i);
 if (!map.containsKey(curr)) {
 map.put(curr, new ArrayList());
 }
 map.get(curr).add(i);
 }

 int prev = -1; //前一个字符下标
 for (int i = 0; i < s.length(); i++) {
 char c = s.charAt(i);

 if (map.get(c) == null) {
 return false;
 } else {
 List list = map.get(c);
 prev = binarySearch(prev, list, 0, list.size() - 1);
 if (prev == -1) {
 return false;
 }
 prev++;
 }
 }

 return true;
}
//二分查找用来提高查找下标的效率
private int binarySearch(int index, List list, int start, int end) {
 while (start <= end) {
 int mid = start + (end - start) / 2;
 if (list.get(mid) < index) {
 start = mid + 1;
 } else {
 end = mid - 1;
 }
 }

 return start == list.size() ? -1 : list.get(start);
}

本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.souzhinan.com/kj/281616.html

392. 判断子序列续（leetcode 解题）

相关推荐