首页 > 代码库 > [leetcode] Interleaving String
[leetcode] 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.
https://oj.leetcode.com/problems/interleaving-string/
1. dfs枚举。
2. DP。dp[i][j]表示s1长度为i字符串和s2长度为j字符串能否组成s3的i+j长度的字符串。
初始化：第一行和第一列。
递推：dp[i][j] == true if dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1) or dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)
public class Solution { // dp public boolean isInterleave(String s1, String s2, String s3) { if (s1 == null || s2 == null || s3 == null) return false; int m = s1.length(); int n = s2.length(); if (m + n != s3.length()) return false; boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int i = 1; i <= m; i++) { dp[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1)) && dp[i - 1][0]; } for (int j = 1; j <= n; j++) { dp[0][j] = (s2.charAt(j - 1) == s3.charAt(j - 1) && dp[0][j - 1]); } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) dp[i][j] = true; if (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) dp[i][j] = true; } } return dp[m][n]; } // dfs public boolean isInterleave2(String s1, String s2, String s3) { if (s1.length() + s2.length() != s3.length()) return false; return rec(s1, 0, s2, 0, s3, 0); } private boolean rec(String s1, int p1, String s2, int p2, String s3, int p3) { if (p3 == s3.length()) return true; if (p1 == s1.length()) return s2.substring(p2).equals(s3.substring(p3)); if (p2 == s2.length()) return s1.substring(p1).equals(s3.substring(p3)); if (s1.charAt(p1) == s3.charAt(p3) && s2.charAt(p2) == s3.charAt(p3)) return rec(s1, p1 + 1, s2, p2, s3, p3 + 1) || rec(s1, p1, s2, p2 + 1, s3, p3 + 1); else if (s1.charAt(p1) == s3.charAt(p3)) return rec(s1, p1 + 1, s2, p2, s3, p3 + 1); else if (s2.charAt(p2) == s3.charAt(p3)) return rec(s1, p1, s2, p2 + 1, s3, p3 + 1); else return false; } public static void main(String[] args) { String s1 = "aabcc"; String s2 = "dbbca"; String s3 = "aadbbcbcac"; String s4 = "aadbbbaccc"; System.out.println(new Solution().isInterleave(s1, s2, s3)); }}
参考：
http://blog.csdn.net/u011095253/article/details/9248073
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。