leetcode392--判断子序列

本文主要是介绍leetcode392--判断子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题意

判断字符串$s$是否为$t$的子序列

2. 题解

2.1 双指针

对于在$t$中找到的$s[i]$字符，我们只需要找下一个即可。

即一个指针$i$指向$s$，一个指针$j$指向$t$;

• $s[i]==t[j],i\leftarrow i+1,j\leftarrow j+1$
• $s[i]\ne t[j],i\leftarrow i+1$

代码

class Solution {
public:bool isSubsequence(string s, string t) {int slen = s.size();int tlen = t.size();if ( slen > tlen)return false;int i = 0;int j = 0;while ( i < slen && j < tlen ) {if (s[i] == t[j])++i,++j;else {++j;}}return i == slen; }
};

2.2 双指针+预处理

我们可以预处理$j$，当$s[i]\ne t[j]$,$j$跳到下一个邻近$s[i]$表示字符出现的位置。

预处理我们可以从后往前遍历；得到转移方程

$$dp[i][j]=\{\begin{array}{l}dp[i+1][j],c={=}^{\prime }{a}^{\prime }+j\\ i,c{\ne }^{\prime }{a}^{\prime }+j\end{array}$$

$dp[i][j]$表示在字符串$t$中的$i$位置与其右端最邻近的$j{+}^{\prime }{a}^{\prime }$字符的位置。

这个dp数组的作用，是来加速上面双指针中$j$指针的跳转。

class Solution {
public:bool isSubsequence(string s, string t) {int n = s.size();int m = t.size();vector<vector<int>> dp(m + 1, vector<int>(26, m));for (int i = m - 1; ~i ; --i) {for (int j = 0;j < 26; ++j) {if ( j + 'a' == t[i]) {dp[i][j] = i;}else {dp[i][j] = dp[i + 1][j];}}}int i = 0;int j = 0;while (i < n && j < m) {if (s[i] == t[j]) {i++;j++;}else {j = dp[j][s[i] - 'a'];}}return i == n; }
};

2.3 动态规划

可以转换为经典的$LCS(longestcommonsequence)$最长公共子序列问题，

即$LCS(s,t)=s.size()$

class Solution {
public:bool isSubsequence(string s, string t) {if (s.empty())return true;int m = static_cast<int>( s.size() );int n = static_cast<int>( t.size() );vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (int i = 1;i <= m; ++i) {for ( int j = 1; j <= n; ++j) {if (s[i - 1] == t[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max( dp[i][j - 1], dp[i - 1][j]);}}return dp[m][n] == m;}
};

这篇关于leetcode392--判断子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---