请教一道刚面到的题string decompression

您好！
本帖隐藏的内容需要积分高于 50 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 50 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

leetcode 原题吧 394. Decode String

oio14644 发表于 2018-6-9 21:09
leetcode 原题吧 394. Decode String

ls够快

的确是原题 这题没写过的话第一次写很可能会出bug的
类似的题目

您好！
本帖隐藏的内容需要积分高于 27 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 27 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

可以了解一下

补充内容 (2018-6-9 21:29):
错了。。不是很类似

谢谢啦，这题一问到就想到slack， 递归不太会， 果然是原题，没做过。。。

承认， 这道题是有点不好想。。

我写了蛮久的还

先说简单的stack想法吧， 我是用一个stack装前面的string， 另一个stack装'['前面的数字。 这样每遇到一个']'的时候就可以反算新的字符串了。代码如下

1.     public String decodeString(String s) {
   
2.         Stack<String> str = new Stack<>();
   
3.         Stack<Integer> count = new Stack<>();
   
4.         int val = 0;
   
5.         String curStr = "";
   
6.         for(char c : s.toCharArray())
   
7.         {
   
8.             if('0' <= c && c <= '9')
   
9.                 val = val * 10 + c - '0';
   
10.             else if(c == '[') // treat as new string, reset counter and current string
    
11.             {
    
12.                 str.push(curStr);
    
13.                 curStr = "";
    
14.                 count.push(val);
    
15.                 val = 0;
    
16.             }
    
17.             else if(c == ']')
    
18.             {
    
19.                 int append = count.pop();
    
20.                 String appendStr = str.pop();
    
21.                 while(append-->0)
    
22.                     appendStr += curStr;
    
23.                 curStr = appendStr; // 我这一块一直搞错， 一直觉得应该进栈， 最后返回是stack.pop(). 后来发现这样不对， 因为current string就没办法更新了。 有点试错的感觉， 这段逻辑写的不好
    
24.             }
    
25.             else curStr += c; // [a-zA-Z]
    
26.         }
    
27.         return curStr;
    
28.     }

复制代码

当然了， 你需要recursion的写法。 上面就是用stack 写出来而已 ，所以用递归的方法也完全没有问题。

1.         public String decodeString( String s )
   
2.         {
   
3.                 return decode( s, "", 0 );
   
4.         }
   
5. 
   
6.         String decode( String s, String apd, int v )
   
7.         {
   
8.                 if ( s.length() < 1 ) return apd;
   
9.                 if ( s.charAt( 0 ) == '[' )
   
10.                 {
    
11.                         // take care of ']' case
    
12.                         int i = 1, k = 1; // for [] balance
    
13.                         while ( k > 0 )
    
14.                         {
    
15.                                 if ( s.charAt( i ) == '[' ) k++;
    
16.                                 if ( s.charAt( i ) == ']' ) k--;
    
17.                                 i++;
    
18.                         }
    
19.                         // i will be position after ']', thus -= 1
    
20.                         i -= 1;
    
21.                         String dcd = decode( s.substring( 1, i ), "", 0 );
    
22.                         while ( v-- > 0 ) apd += dcd;
    
23.                         return decode( s.substring( i + 1 ), apd, 0 );
    
24.                 }
    
25.                 else if ( '0' <= s.charAt( 0 ) && s.charAt( 0 ) <= '9' )
    
26.                 {
    
27.                         return decode( s.substring( 1 ), apd, v * 10 + s.charAt( 0 ) - '0' );
    
28.                 }
    
29.                 return decode( s.substring( 1 ), apd + s.charAt( 0 ), v );
    
30.         }

复制代码

对的，两个stack方法面试的时候如果没做过这题，最直观的就是能想出来。然后通过stack推recursion就觉得好像难度也还OK， 但是边界和要带的参数挺多。直接上来写递归就觉得有点难，我觉得这是道挺好的题