求：

給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

你可以認(rèn)為 s 和 t 中僅包含英文小寫字母。字符串 t 可能會(huì)很長(長度 ~= 500,000)，而 s 是個(gè)短字符串(長度 <=100)。

字符串的一個(gè)子序列是原始字符串刪除一些(也可以不刪除)字符而不改變剩余字符相對(duì)位置形成的新字符串。(例如，"ace"是"abcde"的一個(gè)子序列，而"aec"不是)。

示例?1:

s = "abc", t = "ahbgdc"

返回?true.

示例?2:

s = "axc", t = "ahbgdc"

返回?false.

解：

1、雙指針

利用2個(gè)指針分別遍歷字符串s和字符串t，直到某個(gè)字符串遍歷完成。使用一個(gè)遍歷findCount來記錄匹配字符數(shù)，findCount初始化為0，遍歷過程中如果發(fā)現(xiàn)字符匹配，findCount加1。退出時(shí)判斷findCount是否與字符串s的長度相等，相等說明是子串，否則不是子串。

時(shí)間復(fù)雜度：O(M+N)，M為字符串s長度，N為字符串t長度，因?yàn)镹遠(yuǎn)大于M，可以近似為O(N)

空間復(fù)雜度：O(1)

bool isSubsequence(char* s, char* t){

inti,j;intfindCount = 0;for(i=0,j=0;i

if(s[i]==t[j]){

++i;++findCount;}

}

returnfindCount == strlen(s);}

2、雙指針優(yōu)化

不計(jì)算字符串s和字符串t的長度，直接比。退出的條件是字符串s或字符串t遍歷完成。

時(shí)間復(fù)雜度：O(M+N)，M為字符串s長度，N為字符串t長度，因?yàn)镹遠(yuǎn)大于M，可以近似為O(N)

空間復(fù)雜度：O(1)

bool isSubsequence(char* s, char* t){

while(1){

if(!*s) return true;if(!*t) return false;if(*t++ == *s) s++;}

}

3、動(dòng)態(tài)規(guī)劃

參考官方題解。

總結(jié)

以上是生活随笔為你收集整理的c语言如何判断是否是子序列,leetcode392(判断子序列)--C语言实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。