[Leetcode][第392题][JAVA][判断子序列][动态规划][双指针]

男娘i 2023-03-01 13:54 25阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 双指针 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

**时间复杂度：O(N+M) 空间复杂度：O(1)**  
![在这里插入图片描述][20200727113503984.png]

class Solution { 
    public:
        bool isSubsequence(string s, string t) { 
            int n = s.length(), m = t.length();
            int i = 0, j = 0;
            while (i < n && j < m) { 
                if (s[i] == t[j]) { 
                    i++;
                }
                j++;
            }
            return i == n;
        }
    };

###### 2. 动态规划（后续挑战 ） ######

第 1 步：设计状态  
f\[i\]\[j\] 表示字符串 tt 中从位置 ii 开始往后字符 jj 第一次出现的位置  
第 2 步：状态转移方程  
![在这里插入图片描述][20200727113930921.png]

第 3 步：考虑初始化  
//终止判断标志  
for (int i = 0; i < 26; i++) \{  
f\[m\]\[i\] = m;  
\}  
第 4 步：考虑输出

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public boolean isSubsequence(String s, String t) { 
            int n = s.length(), m = t.length();
    
            int[][] f = new int[m + 1][26];
            for (int i = 0; i < 26; i++) { 
                f[m][i] = m;
            }
    
            for (int i = m - 1; i >= 0; i--) { 
                for (int j = 0; j < 26; j++) { 
                    if (t.charAt(i) == j + 'a')
                        f[i][j] = i;
                    else
                        f[i][j] = f[i + 1][j];
                }
            }
            int add = 0;
            for (int i = 0; i < n; i++) { 
                if (f[add][s.charAt(i) - 'a'] == m) { 
                    return false;
                }
                add = f[add][s.charAt(i) - 'a'] + 1;
            }
            return true;
        }
    }

#### 【总结】 ####

###### 1. 动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2.动态规划方案避免了每次匹配都需要扫描一遍 T ，每处理一次子串只需要扫描一遍Si即可 ######

转载链接：https://leetcode-cn.com/problems/is-subsequence/solution/pan-duan-zi-xu-lie-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230208/07e895b1a3ef40f3a2ce548827e35338.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230208/ec22eeda1de84ed7a015761a60bf19bd.png
[20200727113503984.png]: /images/20230208/1b3ae03e3b1c4628ad18eb5a8cb4c421.png
[20200727113930921.png]: https://img-blog.csdnimg.cn/20200727113930921.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200727113820546.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200727113806894.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70