首页 > 代码库 > [leetcode]_Interleaving String

[leetcode]_Interleaving String

2024-07-07 08:29:58   225人阅读

下午去蹭了一发新浪的笔试。

炒鸡多的网络基础知识，总共18道题，就写了8道左右吧，剩下的全是网络知识，这部分抽时间至少过一过。

其中一道算法题，回来跟嘟嘟商量，才发现是leetcode上的原题，连example都没有变，这可是道难度系数5的题，我嘞个去。

题目：给定三个字符串s1,s2,s3，判断s3是否能由s1和s2交错而成。

思路：

1、当s1当前字符 = s2当前字符 && s2当前字符 != s3当前字符 时，消s1.

2、同理状况 消s2.

3、难点在于当s1当前字符 = s2当前字符 = s3当前字符时，消谁，消错了可能引发后面的错误。我当时就想，那索性都尝试一遍，于是很直接的递归的想法就这么形成的。

 1    public boolean isInterleave(String s1, String s2, String s3) {
 2         
 3         int len1 = s1.length();
 4         int len2 = s2.length();
 5         int len3 = s3.length();
 6         if(len1 + len2 != len3) return false;
 7         else return isInterleaveCore(s1 , 0 , len1 - 1 , s2 , 0 , len2 - 1 , s3 , 0 , len3 - 1);
 8         
 9     }
10     public boolean isInterleaveCore(String s1 , int s1Start , int s1End , 
11                                     String s2 , int s2Start , int s2End , 
12                                     String s3 , int s3Start , int s3End){
13                                         
14         int p1 = s1Start , p2 = s2Start , p3 = s3Start;
15         while(p3 <= s3End){
16             char ch3 = s3.charAt(p3);
17             if(p1 <= s1End && p2 <= s2End){
18                 char ch1 = s1.charAt(p1);
19                 char ch2 = s2.charAt(p2);
20                 if(ch1 == ch3 && ch2 != ch3){
21                     p1++;
22                     p3++;
23                 }else if(ch1 != ch3 && ch2 == ch3){
24                     p2++;
25                     p3++;
26                 }else if(ch1 != ch3 && ch2 != ch3){
27                     return false;
28                 }else{
29                     return isInterleaveCore(s1 , p1 + 1 , s1End , s2 , p2 , s2End , s3 , p3 + 1 , s3End) ||
30                            isInterleaveCore(s1 , p1 , s1End , s2 , p2 + 1, s2End , s3 , p3 + 1 , s3End);
31                 }
32             }else if(p1 <= s1End){
33                 char ch1 = s1.charAt(p1);
34                 if(ch1 != ch3) return false;
35                 else{
36                     p1++;
37                     p3++;
38                 }
39             }else if(p2 <= s2End){
40                 char ch2 = s2.charAt(p2);
41                 if(ch2 != ch3) return false;
42                 else{
43                     p2++;
44                     p3++;
45                 }
46             }
47         }
48         return true;
49     }

 

这里为自己点一个赞。第一次在考试中把递归给写出来了，证明之前的练习还是很成效的。非常( ^_^ )不错嘛。

但是这个算法过大集合时超时。其时间复杂度太高了。

 

网络上讲解还是要用DP。不会的心服口服。除了多练还是多练。


联系
我们