394. Decode String

Posted on | Edited on | Views:

LeetCode

Recursion

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
// my own solution to this question
class Solution {
    private int findR(String s, int l) {
        while (Character.isLetter(s.charAt(l))) {
            l++;
        }
        return l;
    }
    
    private int[] findNumStartAndCnt(String s,int l){
        int i=l;
        while (i>=0&&Character.isDigit(s.charAt(i))) {
            i--;
        }
        return new int[]{i+1,Integer.valueOf(s.substring(i+1,l+1))};
    }

    public String decodeString(String s) {
        int lastIndexL=s.lastIndexOf("[");
        if(lastIndexL<0){
            return s;
        }else{
            int indexR=findR(s,lastIndexL+1);
            int[] numStartAndCnt=findNumStartAndCnt(s, lastIndexL-1);
            int cnt=numStartAndCnt[1];
            String tmp="",subStr=s.substring(lastIndexL+1,indexR);
            for(int i=0;i<cnt;i++){
                tmp+=subStr;
            }
            return decodeString(s.substring(0,numStartAndCnt[0])+tmp+s.substring(indexR+1));
        }
    }
}

link
Solution from discussion, Recursion with 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
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();
    }
}

0%