[leetcode] Interleaving String | 看string是不是另外两个string穿插得到的
Posted July 19, 2013
on:卧槽这道还真自己做出来了。感觉是二维DP,尽管没让求什么最大最小个数之类的,只是boolean,但是递推关系还是有的。其实只要把状态敢于定义出来(旁边标注物理意义),状态转移方程就能写出来了。然后就是处理最开始。思路:
- 一开始是这么定义的: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的。
- 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个能成功)
- 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()]; }
April 1, 2014 at 7:30 pm
NB