GuilinDev

Lc1190

05 August 2008

1190 Reverse Substrings Between Each Pair of Parentheses

有小写字母和小括号，先reverse最里面的小写字母，去掉括号，再reverse外面一层的小写字母，以此类推

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

class Solution {
    public String reverseParentheses(String s) {
        int begin = 0;
        int end;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(')
                begin = i;
            if(s.charAt(i) == ')'){
                end = i;
                String temp = s.substring(begin + 1, end);
                return reverseParentheses(s.substring(0, begin) + reverseString(temp) + s.substring(end + 1));
            }
        }
        return s;
    }

    String reverseString(String s){
        char[] temp = s.toCharArray();
        StringBuilder r = new StringBuilder();
        for (int i = temp.length-1; i>=0; i--)
            r.append(temp[i]);

        return r.toString();
    }
}

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public String reverseParentheses(String s) {
        if(s.length() == 0) return "";
        
        int begin = 0, end = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') begin = i;
            if(s.charAt(i) == ')') {
                end = i;
                StringBuilder sb = new StringBuilder(s.substring(begin+1, end));
                return reverseParentheses(s.substring(0, begin) + sb.reverse().toString() + s.substring(end+1));
            }
        }
        return s;
    }
}
This site is open source. Improve this page.