【leetcode刷題】T175-判斷子序列

• 2019 年 10 月 4 日
• 筆記

【題目】

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

你可以認為 s 和 t 中僅包含英文小寫字母。字元串 t 可能會很長（長度 ~= 500,000），而 s 是個短字元串（長度 <=100）。

字元串的一個子序列是原始字元串刪除一些（也可以不刪除）字元而不改變剩餘字元相對位置形成的新字元串。（例如，"ace"是"abcde"的一個子序列，而"aec"不是）。

示例 1:  s = "abc", t = "ahbgdc"  返回 true.    示例 2:  s = "axc", t = "ahbgdc"  返回 false.

【思路】

本題較為簡單，直觀來說，對於s中的每個字元，遍歷是否依次在t中出現。

不太好說，看程式碼~~

【程式碼】

python版本

class Solution(object):      def isSubsequence(self, s, t):          """          :type s: str          :type t: str          :rtype: bool          """          if len(s) > len(t):              return False          j = 0          for si in s:              while j < len(t):                  if si == t[j]:                      break                  j += 1              if j >= len(t):                  return False              j += 1          return True

C++版本

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