leetCode练习（97）

科技前沿 • 2025-03-16 15:20 • 阅读 29

大家好，我是讯享网，很高兴认识大家。

题目：Interleaving String

难度：hard

问题描述：

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.

解题思路：判断s3是否由s1、s2顺序插入形成。

一开始使用了DFS回溯法，很简单，结果超时。这里放上代码：

讯享网

public static boolean isInterleave(String s1, String s2, String s3) { if(s3.equals("")){ if(s1.equals("")&&s2.equals("")){ return true; }else{ return false; } } if(s1.equals("")){ return s2.equals(s3); } if(s2.equals("")){ return s1.equals(s3); } char c1=s1.charAt(0); char c2=s2.charAt(0); char c3=s3.charAt(0); if(c3==c1){ boolean temp=isInterleave(s1.substring(1),s2,s3.substring(1)); if(c3==c2){ return temp|| isInterleave(s1,s2.substring(1),s3.substring(1)); }else{ return temp; } }else{ if(c3==c2){ return isInterleave(s1,s2.substring(1),s3.substring(1)); }else{ return false; } } }

讯享网

想想也是，字符串长度太大，DFS指数增长太可怕。这时看到提示使用动态规划。想到了可以使用二维动态规划。

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"

对于Table[I][j],若table[I-1][j]=1且s2[j]=s3[I+1-1];或者table[I][j-1]=1且s1[I]=s3[I+j-1] ,那么Table[I][j]=1，否则=0；

具体代码如下：

讯享网public static boolean isInterleave2(String s1, String s2, String s3) { if(!(s1.length()+s2.length()==s3.length())){ return false; } if(s1.equals("")||s2.equals("")){ return s3.equals(s1+s2); } if(s3.equals("")){ return false; } boolean[] row=new boolean[s1.length()]; boolean[] column=new boolean[s2.length()]; for(int i=0;i<row.length;i++){ if(s1.charAt(i)==s3.charAt(i)) row[i]=true; else break; } for(int i=0;i<column.length;i++){ if(s2.charAt(i)==s3.charAt(i)) column[i]=true; else break; } for(int i=0;i<row.length;i++){ for(int j=0;j<column.length;j++){ if((row[i]&&s2.charAt(j)==s3.charAt(i+j+1))||(column[j]&&s1.charAt(i)==s3.charAt(i+j+1))){ column[j]=true; row[i]=true; }else{ column[j]=false; row[i]=false; } } } return column[s2.length()-1]; }

leetCode练习（97）

相关推荐