leetcode 97 交错字符串

leetcode 97 交错字符串

1-----这里不要认为交错字符串有什么特别的顺序要求，如果我们一个字符一个字符的处理，那么就不用管是不是交错字符串了啊

    public boolean isInterleave(String s1, String s2, String s3) {if(s1.length()+s2.length()!=s3.length())return false;return isInterleave_index(s1,s2,s3,0,0,0);}public boolean isInterleave_index(String s1,String s2,String s3,int x,int y,int z){System.out.println(s1.substring(x)+" "+s2.substring(y)+" "+s3.substring(z));if(z>=s3.length())return true;if(x<s1.length()&&s1.charAt(x)==s3.charAt(z)&&isInterleave_index(s1,s2,s3,x+1,y,z+1))return true;if(y<s2.length()&&s2.charAt(y)==s3.charAt(z)&&isInterleave_index(s1,s2,s3,x,y+1,z+1))return true;return false;}

2----DP解决---这里真的很巧妙-----官网的题解中的动画也很好

dp[i][j]表示s1的前i个字符和s2的前j个字符是否能构成s3的前i+j个字符。。。。感觉再做点DP可以总结一点DP的思路

其实我们很容易想到常用算法DP,也知道用一个二维数组，但是经常不知道这个二维数组里面每个元素表示什么！但感觉做多了会有规律可循;而当我们假定里面的每个元素表示什么的时候，我们需要给出动态规划的状态转移，才能佐证我们的假定是正确的hhh

3----DP----常常N*M都可以用滚动数组解决，降低一点空间复杂度。。但是一般还是喜欢用N*M二维数组来理解。