这是农行软件研发中心的笔试题
也是leetcode 97. Interleaving String
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
样例 比如 s1 = "aabcc" s2 = "dbbca" 当 s3 = "aadbbcbcac"，返回 true.当 s3 = "aadbbbaccc"， 返回 false.
还是两种套路
class Solution_ConsitsString0707{ //这里的F(n,m)代表s1[0..n],s2[0..m]是否可以构成s3[0..n+m+1];因为需要全部的进行匹配n+1的长度m+1的长度 //终止条件n==-1,表示s1字符串已经没有了，变成了s2[0..m]是否可以构成s3[0..m] //终止条件m==-1,表示s2字符串已经没有了，变成了s1[0..n]是否可以构成s3[0..n] private boolean isConsist(String s1,String s2,String s3,int n,int m){ if(n == -1){ return s2.substring(0,m+1).equals(s3.substring(0,m+1)); } if(m == -1){ return s1.substring(0,n+1).equals(s3.substring(0,n+1)); } if(s1.charAt(n)== s3.charAt(m+n+1)&& isConsist(s1,s2,s3,n-1,m)|| s2.charAt(m) == s3.charAt(m+n+1)&& isConsist(s1,s2,s3,n,m-1)){ return true; } return false; } public boolean isConsist(String s1,String s2,String s3){ int n = s1.length(); int m = s2.length(); if(n+m != s3.length())return false; if(n==0&&m==0)return s3.length()==0; if(n==0)return s2.equals(s3); if(m==0)return s1.equals(s3); return isConsist(s1,s2,s3,n-1,m-1); } //这里memo[i][j]表示，s1[0..i-1],s2[0..j-1]是否可以构成s3[0..i+j-1] //memo[0][j]表示,s1[0..-1]也就是不存在了，s2[0..j]是否可以构成s3[0..j] //memo[i][0]表示s1[0..i],s2[0..-1]也就是不存在了，是否可以构成s3[0..i] //最后返回memo[n][m]表示s1[0..n-1],s2[0..m-1]是否可以构成s3[0..n+m-1] //因为没有办法表示[-1][i]所以只能拓展[n][m] public boolean isConsistDy(String s1,String s2,String s3){ int n = s1.length(); int m = s2.length(); if(s1.length()+s2.length() != s3.length())return false; if(n==0&&m==0)return s3.length()==0; if(n==0)return s2.equals(s3); if(m==0)return s1.equals(s3); //也就是说要执行下面两个字符串必须有字符 boolean[][] memo = new boolean[n+1][m+1]; //代表的是索引 for(int i = 1;i<=n;i++){ if(s1.substring(0,i).equals(s3.substring(0,i))){ memo[i][0] = true; } } for(int j = 1;j<=m;j++){ if(s2.substring(0,j).equals(s3.substring(0,j))){ memo[0][j] = true; } } for(int i = 1;i<=n;i++){ for(int j=1;j<=m;j++){ memo[i][j] = ((s1.charAt(i-1)==s3.charAt(i+j-1)&&memo[i-1][j]) || (s2.charAt(j-1)==s3.charAt(i+j-1)&&memo[i][j-1])); } } return memo[n][m]; } }