97. Interleaving String

97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example, Given: s1 = “aabcc”, s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true. When s3 = “aadbbbaccc”, return false.

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

class Solution { public boolean isInterleave(String s1, String s2, String s3) { char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); char[] c3 = s3.toCharArray(); if (c1.length+c2.length != c3.length) return false; int[][] dp = new int[c1.length+1][c2.length+1]; return isValid(c1, c2, c3, 0, 0, dp); } boolean isValid(char[] c1, char[] c2, char[] c3, int s1, int s2, int[][] dp) { if (s1==c1.length && s2==c2.length) return true; int s3 = s1+s2; if (dp[s1][s2] == 1) return true; else if (dp[s1][s2] == -1) return false; if (s1

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。