本文主要是介绍LeetCode——Interleaving String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Interleaving String
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
Java代码：
public class Solution {public boolean isInterleave(String s1, String s2, String s3) {int s1_len = s1.length();int s2_len = s2.length();int s3_len = s3.length();if((s1_len+s2_len)!= s3_len) return false;if(s1 == null || s2 == null || s3==null)return false;if(s3.equals("")) return true;if(s1.equals("") && s2.equals(""))return false;if(!(s1.equals("")) && !(s2.equals(""))){if(s3.charAt(0) == s1.charAt(0) || s3.charAt(0)==s2.charAt(0)){if(s3.charAt(0) == s1.charAt(0) && s3.charAt(0)==s2.charAt(0)){if(!isInterleave(s1.substring(1), s2, s3.substring(1)))if(!isInterleave(s1, s2.substring(1), s3.substring(1)))return false;}else if(s3.charAt(0) == s1.charAt(0)){if(!isInterleave(s1.substring(1), s2, s3.substring(1)))return false;}else{if(!isInterleave(s1, s2.substring(1), s3.substring(1)))return false;}}else{return false;}}else if(!s1.equals("")){if(s3.charAt(0) == s1.charAt(0)){if(!isInterleave(s1.substring(1), s2, s3.substring(1)))return false;}else{return false;}}else{if(s3.charAt(0) == s2.charAt(0)){if(!isInterleave(s1, s2.substring(1), s3.substring(1)))return false;}else{return false;}}return true;}
}
public class Solution {public boolean isInterleave(String s1, String s2, String s3) {int s1_len = s1.length();int s2_len = s2.length();int s3_len = s3.length();if((s1_len+s2_len)!= s3_len) return false;if(s1 == null || s2 == null || s3==null)return false;if(s3.equals("")) return true;if(s1.equals("") && s2.equals(""))return false;if(!(s1.equals("")) && !(s2.equals(""))){if(s3.charAt(0) == s1.charAt(0) || s3.charAt(0)==s2.charAt(0)){if(s3.charAt(0) == s1.charAt(0) && s3.charAt(0)==s2.charAt(0)){if(!isInterleave(s1.substring(1), s2, s3.substring(1)))if(!isInterleave(s1, s2.substring(1), s3.substring(1)))return false;}else if(s3.charAt(0) == s1.charAt(0)){if(!isInterleave(s1.substring(1), s2, s3.substring(1)))return false;}else{if(!isInterleave(s1, s2.substring(1), s3.substring(1)))return false;}}else{return false;}}else if(!s1.equals("")){if(s3.charAt(0) == s1.charAt(0)){if(!isInterleave(s1.substring(1), s2, s3.substring(1)))return false;}else{return false;}}else{if(s3.charAt(0) == s2.charAt(0)){if(!isInterleave(s1, s2.substring(1), s3.substring(1)))return false;}else{return false;}}return true;}
}代码提交之后，测试库里面有一组很长的字符串数组，结果“Time Limit Exceeded”
原题的要求应该是使用时间复杂度更低的算法实现。
用动态规划的java实现：
public class Solution {public boolean isInterleave(String s1, String s2, String s3) {String min_string = s1.length()>s2.length()?s2:s1;String max_string = s1.length()>s2.length()?s1:s2;boolean [][] val = new boolean [min_string.length()+1][max_string.length()+1];if((s1.length()+s2.length())!=s3.length())return false;for(int i=0;i<=min_string.length();i++)for(int j=0;j<=max_string.length();j++)val[i][j] =false;val[0][0] = true;for(int i =1;i<=min_string.length();i++)if(s3.charAt(i-1) == min_string.charAt(i-1))val[i][0] =true;elsebreak;for(int j=1;j<=max_string.length();j++)for(int i=0;i<=min_string.length();i++)if(i ==0){if(val[i][j-1]==true && s3.charAt(i+j-1)==max_string.charAt(j-1))val[i][j] =true;}else{if((val[i-1][j]==true && s3.charAt(j+i-1)==min_string.charAt(i-1)) ||(val[i][j-1]==true && s3.charAt(i+j-1)==max_string.charAt(j-1)))val[i][j] =true;}if(val[min_string.length()][max_string.length()]==true)return true;else return false;}
}做了一下运行时间的对比
代码一：13261ms 代码二：2ms
这篇关于LeetCode——Interleaving String的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
