Interleaving String
给三个字符串, S1,S2,S3. 问S3是不是S1和S2交叉在一起. 这个题用dp来做. dp[i][j] 表示s1的前i和s2的前j个字符能组成s3的前i+j个字符. 那么是true. 这个dp最难的是初始化.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { // Note: The Solution object is instantiated only once and is reused by each test case. if (s1 == null || s2 == null || s3 == null) return false; if (s1.length() + s2.length() != s3.length()) return false; boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1]; dp[0][0] = true; for(int i = 1; i < s1.length() + 1; i++) { if (s1.charAt(i - 1) == s3.charAt(i - 1) && dp[i - 1][0]) { dp[i][0] = true; } } for(int j = 1; j < s2.length() + 1; j++) { if (s2.charAt(j - 1) == s3.charAt(j - 1) && dp[0][j - 1]) { dp[0][j] = true; } } for(int i = 1; i < s1.length() + 1; i++) { for(int j = 1; j < s2.length() + 1; j++) { if (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) { dp[i][j] = true; } if (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]) { dp[i][j] = true; } } } return dp[s1.length()][s2.length()]; } } |