Example 1:
Input: s = “3[a]2[bc]” Output: “aaabcbc” Example 2:
Input: s = “3[a2[c]]” Output: “accaccacc” Example 3:
Input: s = “2[abc]3[cd]ef” Output: “abcabccdcdcdef”
用栈
public class Solution { public String decodeString(String s) { String res = ""; Stack<Integer> countStack = new Stack<>(); Stack<String> resStack = new Stack<>(); int idx = 0; while (idx < s.length()) { if (Character.isDigit(s.charAt(idx))) { int count = 0; while (Character.isDigit(s.charAt(idx))) { count = 10 * count + (s.charAt(idx) - '0'); idx++; } countStack.push(count); } else if (s.charAt(idx) == '[') { resStack.push(res); res = ""; idx++; } else if (s.charAt(idx) == ']') { StringBuilder temp = new StringBuilder (resStack.pop()); int repeatTimes = countStack.pop(); for (int i = 0; i < repeatTimes; i++) { temp.append(res); } res = temp.toString(); idx++; } else { res += s.charAt(idx++); } } return res; } }recursive
class Solution { public String decodeString(String s) { Deque<Character> queue = new LinkedList<>(); for (char c : s.toCharArray()) queue.offer(c); return helper(queue); } public String helper(Deque<Character> queue) { StringBuilder sb = new StringBuilder(); int num = 0; while (!queue.isEmpty()) { char c= queue.poll(); if (Character.isDigit(c)) { num = num * 10 + c - '0'; } else if (c == '[') { String sub = helper(queue); for (int i = 0; i < num; i++) sb.append(sub); num = 0; } else if (c == ']') { break; } else { sb.append(c); } } return sb.toString(); } }