脚本宝典收集整理的这篇文章主要介绍了LeetCode 394: DecodeString (Java),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
解码题。
编码规则直接看例子(编码后字符串->原字符串):
2[b] -> bb
3[a2[c]] -> 3[acc] -> accaccacc
2[a2[b]ef]xy ->2[abbef]xy->abbefabbefxy
根据上面的结构我们很容易想到用深搜算法:
先将']' 之前的信息(要重复的部分及重复次数)压到stack里,等到了']'再一个一个推出还原。思路非常清晰,但是实现起来并不简单。得注意细节及其处理方式,比如数字可能出现两位及以上; 并列关系[],[]和包含关系[[]]如何巧妙区分。另外发现大循环用while而不是for可能更方便一些。
下面是我在leetcode论坛上找到的比较好看的代码(44%):
public static String decodeString(String s) { Stack<Integer> count = new Stack<>(); Stack<String> result = new Stack<>();//用Stack处理包含关系 result.push(""); int i = 0; while(i<s.length()){ char a = s.charAt(i); if(a >= '0' && a <= '9'){ int p1 = i; while(Character.isDigit(s.charAt(i+1))) i++; count.push(Integer.parseint(s.substring(p1,i+1))); } else if (a == '[') { result.push("");//用初始化空字符串处理并列关系 } else if(a == ']') { String temp = new String(result.pop()); StringBuilder sb = new StringBuilder(); int nloop = count.pop(); for(int j = 0; j < nloop;j++) sb.append(temp); result.push(result.pop()+sb.toString()); } else { result.push(result.pop()+a); } i++; } return result.pop(); }
当然也可以用递归算法,但我感觉比较难想,这种算法比较直接,面试的时候想到比较实际。
以上是脚本宝典为你收集整理的LeetCode 394: DecodeString (Java)全部内容,希望文章能够帮你解决LeetCode 394: DecodeString (Java)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。