Decode String 394

Question

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".

s = "3[a2[c]]", return "accaccacc".

s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Solution

这道题我直接根据遇到的各种情况分别讨论，有点繁琐，之后看看有没有别的好方法再补充。

用两个stack，一个存遇到的数字，一个存遇到的字符串。

1. 如果某一位遇到digit，则从这一位开始往后直到遇到不是数字的那一位停止，这一段substring就是数字，加入数字的stack中

2. 如果某一位遇到"["，则从这一位开始往后直到遇到不是字母的那一位停止，这一段就是需要重复的字符串，加入字符串的stack中

3. 如果某一位遇到"]"，则将数字和字符串stack的栈顶元素出栈，将出栈字符串重复出栈数字次。如果此时字符串stack中还有元素，则取出栈顶元素和重复字符串拼接组成新的字符串，再放回字符串stack中（这是为了考虑s = "3[a2[c]]"这类情况），否则直接放回字符串stack中

4. 如果某一位遇到letter，则说明这个是独立不在[]中的字符串起点（[]中的letter已经被2处理），则从这一位开始往后直到遇到不是字母的那一位停止，这一段就是不需要重复的字符串。如果此时字符串stack中还有元素，则取出栈顶元素和不需要重复字符串拼接组成新的字符串，再放回字符串stack中（这是为了考虑s = "2[abc]3[cd]ef"这类情况），否则直接放回字符串stack中

5. 最后字符串stack中剩下的就是最后结果

代码如下：

public class Solution {
    public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        Stack<Integer> digit = new Stack<Integer>();
        Stack<String> letter = new Stack<String>();

        for (int i = 0; i < s.length();) {
            char curt = s.charAt(i);

            if (Character.isDigit(curt)) {
                int index = i;
                while (index < s.length() && Character.isDigit(s.charAt(index))) {
                    index++;
                }
                String num = s.substring(i, index);
                digit.push(Integer.parseInt(num));
                i = index;
            }

            if (Character.isLetter(curt)) {
                int index = i;
                while (index < s.length() && Character.isLetter(s.charAt(index))) {
                    index++;
                }
                String str = s.substring(i, index);
                if (!letter.isEmpty()) {
                    str = letter.pop() + str;
                }
                letter.push(str);
                i = index;
            }

            if (curt == '[') {
                int index = i + 1;
                while (index < s.length() && Character.isLetter(s.charAt(index))) {
                    index++;
                }
                String str = s.substring(i + 1, index);
                letter.push(str);
                i = index;
            }

            if (curt == ']') {
                int num = digit.pop();
                String app = letter.pop();
                String str = "";
                for (int j = 0; j < num; j++) {
                    str += app;
                }
                if (!letter.isEmpty()) {
                    str = letter.pop() + str;
                }
                letter.push(str);
                i++;
            }
        }

        return letter.pop();
    }
}