精选: 高级解法 判断子序列, 画图解析动态规划, 容易理解

思路与说明:

说明: 当长串t不变, 有大量的短串需要判断 (比如上亿级别的), 使用此法效率非常高, 可以节省大量时间.

注意: 题目原本说字符串只包含小写字母, 但实际测试用例里面有包含了数字字符的, 对如下代码做一些修改后, 也能解决.
  不做修改的话, 只适用于小写字母的情况.
思路: 举例字符串t是"abcabdd", 使用二维数组d[26][t.length()] 来预处理, 
经过预处理后, 再对子串进行判断, 效率将非常高, 分析如下图:

主要对应代码
for (int i = 0; i < 26; i++) {
    d[i][t.length()] = -1;
}

主要对应代码
for (int i = 25; i >= 0; i--) {
    for (int j = t.length() - 1; j >= 0; j--) {
        if (t.charAt(j) - 'a' == i) {
            d[i][j] = j;
        } else {
            d[i][j] = d[i][j + 1];
        }
    }
}

完整代码:

//方法一: 动态规划
public boolean isSubsequence(String s, String t) {
    if (s == null || t == null || s.length() > t.length()) return false;
    int[][] d = new int[26][t.length() + 1];
    for (int i = 0; i < 26; i++) {
        d[i][t.length()] = -1;
    }
    //小循环在外层效率更好, 请思考: 可以只用一层循环吗? 或者还可以减少循环次数吗? 
    for (int i = 25; i >= 0; i--) {
	   //倒序遍历, 从后往前推
        for (int j = t.length() - 1; j >= 0; j--) {
            if (t.charAt(j) - 'a' == i) {
                d[i][j] = j;
            } else {
                d[i][j] = d[i][j + 1];
            }
        }
    }
    int c = 0;  //c是列, 长串t中的索引
    for (int i = 0; i < s.length(); i++) {
        int r = s.charAt(i) - 'a';
        //等于 -1时, 长串t 后面不再有该字符
        if (d[r][c] == -1) {
            return false;
        }
        c = d[r][c] + 1;
    }
    return true;
}

// 方法二
public boolean isSubsequence(String s, String t) {
    if (s.length() > t.length()) return false;
    List<Integer>[] buckets = new List[26];
    for (int i=0; i<t.length(); i++){
        int k = t.charAt(i) - 'a';
        if (buckets[k] == null){
            buckets[k] = new ArrayList<Integer>();
        }
        buckets[k].add(i);
    }
    //长串里上一个匹配的索引
    int preMatchIndex = -2;
    for (int i=0; i<s.length(); i++){
        char ch = s.charAt(i);
        //获取该字符 在长串里对应的所有索引
        List<Integer> list = buckets[ch-'a'];
        if (list == null || list.size() == 0){
            return false;
        }
        int j = find(list, Math.max(i, preMatchIndex+1));
        if (j < 0){
            return false;
        }
        preMatchIndex = list.get(j);
    }
    return true;
}
public int find(List<Integer> list, int target){
    if (list == null || list.size() == 0){
        return -1;
    }
    int left = 0, right = list.size()-1;
    int ans = -1;
    while (left <= right){
        int mid = (left+right)/2;
        //如果目标值<=中间值, 则找到一个元素,
        //然后继续在左半部分找, 看是否还有其他更小的元素 也满足该条件
        if (target <= list.get(mid)){
            ans = mid;
            right = mid-1;
        }else {
            left = mid+1;
        }
    }
    return ans;
} 

//方法三 双指针
public boolean isSubsequence(String s, String t) {
    if (s.length() > t.length()) return false;
    int i=0, j=0;
    while(i<s.length() && j<t.length()){
        //如果在长串中找到一个字符 与短串的相等,
        // i与j都右移一位, 否则只有j右移一位
        if (s.charAt(i) == t.charAt(j)){
            i++;
        }
        j++;
    }
    //上面循环结束后,如果i能到达短串的末尾,
    //说明短串里的字符全都匹配到, 才是子序列
    if ( i==s.length()){
        return true;
    }
    return false;
}

题后挑战与思考:

在对长串进行预处理环节, 可以只遍历一次吗? 或者还可以减少循环次数吗?

欢迎留言与讨论, 相互学习, 相互帮助, 共同进步.

花了很多时间来解的.
如该解法能帮助到您, 或感觉不错, 如有java工作, 欢迎联系推荐下, 或评论区留言, 谢谢.
本人有好几年经验, 目前待业中, 希望能找到java技术岗位的工作.