392题: 判断子序列, 高级解法, 图解动态规划算法, 容易理解

题目描述:

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。两个字符串都只由小写字符组成。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶挑战：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，
你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false

思路:

(方法一: 适用于数据量不大的情况) 因子序列是长串去除了某些字符得到的,
 故子序列里的字符 在长串中一定能找到,
并且在长串中只能单向往右边找, 不能回头,
 故只需循环遍历一次, 不需双重循环
因为在长串中找到的字符, 其位置下标要>=短串的 才符合要求

//方法一 双指针  适用于数据量不大的情况
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;
}

进阶挑战:

说明: 当长串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 = c + 1; 或c = d[r][c+1] 吗?
        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;
}

题后挑战与思考:

对于方法二的 动态规划算法,  时间或空间还可以进一步优化? 在对长串进行预处理环节, 可以只遍历一次吗? 或者还可以减少循环次数吗?  如果子串包含有数字 字符, 使用方法二您可以解决?

此题解 已同步在牛客与力扣

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

如该解法能帮助到您, 或感觉不错, 如有java工作, 
欢迎评论区留言, 或联系推荐下, 谢谢.
本人有好几年经验, 从事java技术岗位的工作.

挑战2：

输入两个正整数数组a, b; 数组a从左到右的顺序, 每次取一个数a[i],
数组b每次从最左边, 或最右边取一个数b[i], 求a[i]*b[i]的和的最大值
每个数只能取一次. 举例:
a = [5, 1, 2, 10];
b = [2, 6, 4, 1];
5*2 + 1*6 + 2*4 + 10*1 = 34
5*1 + 1*2 + 2*4 + 10*6 = 75
上面2种取法, 乘积和都不是最大的, 最大的取法如下
5*2 + 1*1 + 2*4 + 10*6 = 10+1+8+60 = 79

您能正确解决此算法题？