题目链接：decode-string
题目描述 给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
题目分析 基本上，我们可以理解为只用三种情况
字母字符串，直接返回
数字字符串，后边跟了各’[‘，将他的下层返回的字符字符串加倍存储。
‘]’一层结束的标志，返回字符字符串。
算法 栈（Stack） 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 import java.util.*;class Solution public String decodeString (String s) StringBuilder result = new StringBuilder(); LinkedList<String> stack = new LinkedList<String>(); int index = 0 ; while (index < s.length()) { if (Character.isLetter(s.charAt(index))) { StringBuilder cur = new StringBuilder(); while (index < s.length() && Character.isLetter(s.charAt(index))) { cur.append(s.charAt(index)); index++; } stack.push(cur.toString()); } else if (Character.isDigit(s.charAt(index))) { int j = index; while (Character.isDigit(s.charAt(j))) j++; stack.push(s.substring(index, j)); index = j + 1 ; } else { while (index < s.length() && s.charAt(index) == ']' ) { StringBuilder tmp = new StringBuilder(); String s2 = stack.pop(); String s1 = stack.pop(); if (Character.isDigit(s1.charAt(0 ))) { int k = Integer.parseInt(s1); while (k-- > 0 ) { tmp.append(s2); } index++; } else { tmp.append(s1); tmp.append(s2); } stack.push(tmp.toString()); } } } while (!stack.isEmpty()) { result.append(stack.removeLast()); } return result.toString(); } }
深度优先遍历（Depth-first-Search） 事实上，感觉这题不是经典的深搜，更加符合stack的标签，不过理解为深搜也没毛病。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution public String decodeString (String s) StringBuilder result = new StringBuilder(); dfs(s.toCharArray(), 0 , result); return result.toString(); } public int dfs (char [] cc, int start, StringBuilder str) while (start < cc.length) { if (Character.isDigit(cc[start])) { int count = 0 ; while (Character.isDigit(cc[start])) { count = count * 10 + cc[start] - '0' ; start++; } StringBuilder inner = new StringBuilder(); int end = dfs(cc, start + 1 , inner); while (count-- > 0 ) str.append(inner.toString()); start = end; } else if (Character.isLetter(cc[start])) { while (start < cc.length && Character.isLetter(cc[start])) { str.append(cc[start]); start++; } } else { return start + 1 ; } } return start; } }
