394. Decode String

394. Decode String

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".

--------------------------------
恶心的题。
思路：处理String分2种情况 1- 是数字 2- 是字母。
数字的话先取得数字，然后对括号里的字母继续进行读取，如果又遇到数字就递归
字母就没啥好说的，吃了就是

ToDo, 用stack再写一次

class Solution {
    public String decodeString(String s) {
        String rt = "";
        int i = 0;
        
        while (i < s.length()) {
            Pair p = nextWord(s, i);
            i = p.i;
            rt += p.s;
        }
            
        return rt;
    }
    
    private Pair getDigits(String s, int i) {
        String d = "";
        while (Character.isDigit(s.charAt(i))) {
            d += s.charAt(i);
            i++;
        }
        i++;
        
        return new Pair(d, i);
    }
    
    private Pair getWord(String s, int i) {
        String st = "";
        while (i < s.length() && s.charAt(i) != ']') {
            if (Character.isDigit(s.charAt(i))) {
                Pair p = nextWord(s, i);
                st += p.s;
                i = p.i;
            } else {
                st += s.charAt(i);
                i++;
            }
        }
        i++;
        
        return new Pair(st, i);
    }
    
    private Pair getSimpleWord(String s, int i) {
        String st = "";
        while (i < s.length() && !Character.isDigit(s.charAt(i)) && s.charAt(i) != ']') {
            st += s.charAt(i);
            i++;
        }

        return new Pair(st, i);
    }
    
    private Pair nextWord(String s, int i) {
        
        if (Character.isDigit(s.charAt(i))) {
        
            Pair digits = getDigits(s, i);
            i = digits.i;
            
            Pair word = getWord(s, i);
            String st = word.s;
            
            int n = Integer.parseInt(digits.s);
            String rt = "";
            for (int j = 0; j < n; j++) {
                rt += st;
            }
            
            return new Pair(rt, word.i);
            
        }else {
            return getSimpleWord(s, i);
        }
    }
}
            
class Pair{
    public String s;
    public int i;
    public Pair(String s, int i) {
        this.s = s;
        this.i = i;
    }
}

Updated on Dec-23rd-2018
跟上面思路一样，区别在于遇到letter的时候就直接加。这样写起来更简单

class Solution {
    private int i = 0;
    public String decodeString(String s) {
        return dfs(s);
    }
    
    private int getDigit(String s) {
        int rt = 0;
        
        while (Character.isDigit(s.charAt(i))) {
            rt = rt * 10 + (s.charAt(i) - '0');
            i++;
        }
        return rt;
    }
    
    private String dfs(String s) {
        StringBuilder sb = new StringBuilder();
        
        while (i < s.length() && s.charAt(i) != ']') {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int times = getDigit(s);
                
                i++; // '['
                String word = dfs(s);
                
                while (times > 0) {
                    sb.append(word);
                    times--;
                }
                
            }else {
                sb.append(c);        
            }
            i++;
        }
        
        return sb.toString();
    }
}