Java教程

力扣(java)-判断子序列(简单)

本文主要是介绍力扣(java)-判断子序列(简单),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

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

进阶:

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

致谢:

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

 

示例 1:

输入:s = "abc", t = "ahbgdc"
输出:true
示例 2:

输入:s = "axc", t = "ahbgdc"
输出:false
 

提示:

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/is-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

一、双指针

定义两个指针 i 和 j ,并分别指向 s 和 t 的开头,如果当前 i 和 j 位置的字符匹配成功,则 i 和 j 同时后移一位,如果匹配不成功,仅将指向字符串t的指针j向后移动一位即可,i 不变,再进行匹配,如果最后 i = s.length(),则说明匹配成功,否则匹配失败。

代码:

 

二、DP动态规划 

1.先使用动态规划对 t 中的字符位置进行预处理,设t的字符串长度为n,建立一个 n+1*26 大小的矩阵,初始化二维数组的最后一行dp[m][i] 都为n,从后往前填充数组,其他每个位置上的值代表t中每个字符第一次出现的位置;

2.遍历s中的每一个字符,不断地寻找该字符在长字符串中的位置,然后将位置更新,寻找下一个字符。如果下一个位置为 n,表示长字符串再没有该字符了,返回 false 即可。如果能正常遍历完毕,则表示匹配成功,返回 true。

 

代码:

 1 class Solution {
 2     public boolean isSubsequence(String s, String t) {
 3         int n = t.length();
 4         int[][] dp = new int[n+1][26];
 5         //初始化二维数组的最后一行
 6         for(int i = 0; i < 26; i++){
 7             dp[n][i] =  n;
 8         }
 9         //动态填充数组
10         for(int i = n-1; i >= 0; i--){
11             for(int j = 0; j < 26; j++){
12                 if(t.charAt(i) == j + 'a'){
13                     dp[i][j] = i;
14                 }else{
15                     dp[i][j] = dp[i+1][j];
16                 }
17             }
18         }
19         //开始匹配
20         int index = 0;
21         for(int i = 0; i < s.length(); i++){
22             if(dp[index][s.charAt(i) - 'a'] == n){
23                 return false;
24             }
25             index = dp[index][s.charAt(i) - 'a'] + 1;
26         }
27         return true;
28     }
29 }

这篇关于力扣(java)-判断子序列(简单)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!