Lexi's Leetcode solutions

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

Posted on: July 19, 2013

卧槽这道还真自己做出来了。感觉是二维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: ,

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog Stats

  • 222,235 hits
July 2013
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
293031  
%d bloggers like this: