leetcode 392. 判断子序列
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
题解:
1.字符串 s 和 t
2.判断 s 是否为 t 的子序列
3.字符串匹配过程中,相对位置不能改变,剩余字符的匹配必须在前一个字符在t中匹配的位置之后
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
解题思路:
-
以短字符(子序列)为匹配基准,两个工作指针,一个工作s,一个工作t
-
从s的第一个字符开始,在t中查找,不匹配就往后移动直到指针位置上的字符匹配或到达末尾
-
中间判断t中的指针是否已经达到末尾,如果达到末尾就不在判断
C/C++题解:
class Solution {
public:
bool isSubsequence(string s, string t) {
if(s.size() == 0) return true; //s为空时true
if(s.size()>=0 && t.size()==0) return false;//s不空但t为空false
int sx=0, tx = 0;//设两个工作指针
while(sx < s.size()){//以s为基准
//在t中匹配不到就往后走,直到t末尾或匹配到
while(s[sx]!=t[tx] && tx<t.size()) tx += 1;
if(tx == t.size()) break;//t的指针走到末尾不再比较
if(s[sx]==t[tx]) tx += 1;//匹配到字符,t指针往后走
sx += 1;//s字符串指针后移
}//如果s的指针能走到末尾则全匹配上
if(sx == s.size()) return true;
return false; }};//否则不能
Debug结果:
Java题解:
class Solution {
public boolean isSubsequence(String s, String t) {
if(s.length() == 0) return true; //s为空时true
if(s.length()>=0 && t.length()==0) return false;//s不空但t为空false
int sx=0, tx = 0;//设两个工作指针
while(sx < s.length()){//以s为基准
//在t中匹配不到就往后走,直到t末尾或匹配到
while(s.charAt(sx)!=t.charAt(tx) && tx<t.length()) tx += 1;
if(tx == t.length()) break;//t的指针走到末尾不再比较
if(s.charAt(sx)==t.charAt(tx)) tx += 1;//匹配到字符,t指针往后走
sx += 1;//s字符串指针后移
}//如果s的指针能走到末尾则全匹配上
if(sx == s.length()) return true;
return false; }}//否则不能
Debug结果:
Python题解:
class Solution(object):
def isSubsequence(self, s, t):
""":type s: str:type t: str:rtype: bool"""
if len(s) == 0: return True #s为空时true
if len(s)>=0 and len(t)==0: return False #s不空但t为空false
sx, tx =0, 0 #设两个工作指针
while sx < len(s): #以s为基准
#在t中匹配不到就往后走,直到t末尾或匹配到
while s[sx]!=t[tx] and tx<len(t): tx += 1
if tx == len(t): break #t的指针走到末尾不再比较
if s[sx]==t[tx]: tx += 1 #匹配到字符,t指针往后走
sx += 1 #s字符串指针后移
#如果s的指针能走到末尾则全匹配上
if sx == len(s): return True
return False #否则不能
Debug结果:
更多题解移步公众号免费获取