[leetcode] Interleaving String | 看string是不是另外两个string穿插得到的

Posted by: lexigrey on: July 19, 2013

• In: leetcode
• 1 Comment

卧槽这道还真自己做出来了。感觉是二维DP，尽管没让求什么最大最小个数之类的，只是boolean，但是递推关系还是有的。其实只要把状态敢于定义出来（旁边标注物理意义），状态转移方程就能写出来了。然后就是处理最开始。思路：

1. 一开始是这么定义的：d[i][j]: whether s1[0, i]的substring和s2[0, j]的substring能够cross match s3[0, i + j + 1]这个substring。比如ab和c，即(0, 1), (0, 0)，能否合起来是acb(0, 2)。要点是s3的index要+1，这个一开始就想错了直接i + j的。
2. d[i][j] = s3[i + j + 1] == s2[j] && d[i][j – 1] == true （用第s2的j个来填s3的i + j + 1个能成功）， OR s3[i + j + 1] == s1[i] && d[i – 1][j] == true （用第s1的i个来填s3的i + j + 1个能成功）
3. d[i][j]物理意义一定要搞清楚，因为d[0][0]说明拿了两个元素，那么它对应的是长度为2的s3，这index干脆就乱套了。这个时候，换一种方式定义：d[0][0]表示从s1中拿0个，s2中拿0个，然后组成s3（长度为0 + 0)能不能成。这个肯定是true。d[1][0]就能表达只从s1中拿一个，s2中不拿，然后组成长度为1的s3这种make sense的意义了。这样i, j就要一直到=size这么大。所以之前的i + j + 1改成i + j – 1，才能真的往string里charAt。

public boolean isInterleave(String s1, String s2, String s3) {
  if (s3.length() != s1.length() + s2.length())
    return false;
  boolean[][] d = new boolean[s1.length() + 1][s2.length() + 1];
  d[0][0] = true;
  for (int i = 0; i <= s1.length(); i++) {
    for (int j = 0; j <= s2.length(); j++) {
     if (j > 0 && s3.charAt(i + j - 1) == s2.charAt(j - 1) && d[i][j - 1])
       d[i][j] = true;
     else if (i > 0 && s3.charAt(i + j - 1) == s1.charAt(i - 1) && d[i - 1][j])
       d[i][j] = true; 
    }
  }
  return d[s1.length()][s2.length()];
}

Tags: 2WayDP, string