LeetCode 75 Level 1 - Day 2 String

392. Is Subsequence

• 題目連結
• 難易度：Easy

題目敘述

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

預設函數

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

}

題目輸入限制

• 0 <= s.length <= 100
• 
• s and t consist only of lowercase English letters.

解題過程及程式碼

今天是 string 的第二題，題目是給兩個字串 s 和 t，需要判斷出字串 s 是否為字串 t 的 Subsequence，subsequence定義是由字串 t 當中刪除或是不刪除某些字元後是否和字串 s 相同，例如字串 "abcde" 在刪除 b、d 之後是 "ace"，所以 "ace" 就是 "abcde" 的subsequence。

除了昨天說明的string函數：strlen、strcmp以外，我們可以利用strchr函數來判斷字串是否出現在另一個字串中

• 使用strchr函數可以用來找出字串第一個出現的位置，回傳值是字串第一個出現位置的指標，例如以下程式碼，會顯示found at 4。
  • 注意平常寫C語言需要 #include <string.h> 但在Leetcode中不需要
  • 當找不到時函數會回傳a null pointer

  #include <string.h>
  
  int main() {
      char str[] = "This is a sample string";
      char * pch;
  
      pch = strchr(str,'s');
      printf ("found at %d\n", pch - str + 1);  // 1,2,3,第4個位置 
      return 0;
  }
  

• 關於strchr函數可以參考以下網站的說明
  • https://cplusplus.com/reference/cstring/strchr/
  • https://en.cppreference.com/w/cpp/string/byte/strchr

一開始的想法是：從字串 t 當中找出是否有 s[i] 相同的字元，接著確認順序：有相同字元的index必須要越來越大

• 但是此作法無法通過char s[] = "ab"、char t[] = "baab" 測試項目，如下圖Fig.1所示，程式碼如下

  bool isSubsequence(char * s, char * t){
      int i = 0;
      int found_index = 0;
      int max_index = 0;
  
      while (s[i] != '\0') {
          if (strchr(t, s[i]) != NULL) {  // 找不到時會回傳a null pointer
              found_index = (int)(strchr(t, s[i]) - t);
              if (found_index >= max_index) {
                  t[found_index] = 'A';
                  max_index = found_index;
              } else {
                  return 0;
              }
          } else {
              return 0;
          }
          i++;
      }
      return 1;
  }
  

改良後想法是拿 t[i] 來與 s[j] 一個個比較是否相同，如下圖Fig.2所示

• 當 t[i] 和 s[j] 相同時：
  • s[j] = 'A'
  • j++
  • i++
• 當 t[i] 和 s[j] 不同時：i++
• 最後比較 s[ ] 是否全部為'A'

• 程式碼上傳

  bool checkChar(char*);
  
  bool isSubsequence(char * s, char * t){
      int i = 0;
      int s_index = 0;
  
      while (t[i] != '\0') {
          if (t[i] == s[s_index]) {
              s_index++;
              s[s_index - 1] = 'A';
          }
          i++;
      }
      return checkChar(s);    
  }
  
  bool checkChar(char* s) {
      int i = 0;
      while (s[i] != '\0') {
          if ((s[i]) != 'A') {
              return 0;
          }
          i++;
      }
      return 1;
  }