97.Interleaving String

97.Interleaving String

這題要判斷兩個字串交錯後 是否等於第三個字串

雙指針

直覺會使用雙指針來解
如果這題使用雙指針來解的話，會遇到一個問題
如 s1=a, s2=abc, s3=abca
從s1開始移動是False
從s2開始移動是True
這樣會很難決定從哪邊開始移動

動態規劃

這題的正解是動態規劃，只是不太直覺

以上面的例子來說的話，總共有十個數字 題意要交錯
用雙迴圈可以把每個點都走到，一定可以完成交錯的條件
每次的步數只能

1. i+1
2. j+1

每次都去確認雙迴圈的值
如果是左列的數字一樣，那就去判斷[i-1, j]的值
如果是上列的數字一樣，那就去判斷[i, j-1]的值
如果是True代表是已經走過的點。如果是False代表是沒有走過的點
如此就可以重複利用之前走的點，幫助判斷

public boolean isInterleave1(String s1, String s2, String s3) {
  int[][] dq = new int[s1.length()+1][s2.length()+1];
  dq[0][0] = 1;
  if(s1.length()+s2.length() != s3.length())
      return false;
  int idx, flag;
  for (int i = 0; i <= s1.length(); i++) { // <= 是因為沒前綴的初始值是1，索引是0，所以要多loop一次
      for (int j = 0; j <= s2.length(); j++) {
          idx = i+j-1;
          if(i > 0){
              flag = s3.charAt(idx) == s1.charAt(i-1) ? 1 : 0;
              dq[i][j] |= dq[i-1][j] & flag; // |= 是因為 i or j 任何一個是1就是1
          }
          if (j > 0){
              flag = s3.charAt(idx) == s2.charAt(j-1) ? 1 : 0;
              dq[i][j] |= dq[i][j-1] & flag;
          }
      }
  }
  return dq[s1.length()][s2.length()] > 0;
}

後來發現此題有更高的要求，要O(s2.length)的空間複雜度
目前的複雜度是
時間 O(nm)
空間 O(nm)

我去看了題目的解析

public boolean isInterleave2(String s1, String s2, String s3) {
  int[] dq = new int[s2.length() + 1];
  dq[0] = 1;
  if (s1.length() + s2.length() != s3.length())
      return false;
  int idx, flag;
  for (int i = 0; i <= s1.length(); i++) {
      int k = 1;
      for (int j = 0; j <= s2.length(); j++) {
          idx = i + j - 1;
          if (i > 0) {
              flag = s3.charAt(idx) == s1.charAt(i - 1) ? 1 : 0;
              dq[j] = dq[j] & flag;    //  拿掉了|，因為dq已經剩下一維陣列
          }
          if (j > 0) {
              flag = s3.charAt(idx) == s2.charAt((j - 1)) ? 1 : 0;
              if (dq[j] > 0 || (dq[j - 1] & flag) > 0)
                  dq[j] = 1;
              else
                  dq[j] = 0;
          }
      }
  }
  return dq[s2.length()] > 0;
}

核心的理念是
每次只要i loop一次，那個dq就會得到一次最新的值
直到loop到最後一次，dq 就等於之前的 dq[s1.length()]