解码字符串 Decode String

2018-11-14 17:56:12

问题描述：

问题求解：

方法一、递归求解

最直观的解法就是递归来求了，并且很显然的这个问题可以使用递归来进行求解。

    public String decodeString(String s) {

        StringBuffer sb = new StringBuffer();

        int num = 0;

        for (int i = 0; i < s.length(); i++) {

            if (Character.isDigit(s.charAt(i))) {

                num = 0;

                while (i < s.length() && Character.isDigit(s.charAt(i))) {

                    num = num * 10 + (s.charAt(i) - '0');

                    i++;

                }

                i--;

            }

            else if (s.charAt(i) == '[') {

                int count = 1;

                int j = i;

                while (count != 0) {

                    j++;

                    if (s.charAt(j) == '[') count++;

                    if (s.charAt(j) == ']') count--;

                }

                String tmp = decodeString(s.substring(i + 1, j));

                for (int k = 1; k < num; k++) sb.append(tmp);

                i = j;

            }

            else sb.append(s.charAt(i));

        }

        return sb.toString();

    }

方法二、使用Stack求解

使用Stack求解的时候，最核心的思路就是当遇到'['的时候将当前sb 和 num进行压栈操作，当遇到‘]’的时候将堆栈中sb 和 num取出并对当前的字符串进行num次重复并串联到sb后面。

    public String decodeString(String s) {

        StringBuffer sb = new StringBuffer();

        Stack<StringBuffer> stack1 = new Stack<>();

        Stack<Integer> stack2 = new Stack<>();

        int k = 0;

        for (char c : s.toCharArray()) {

            if (Character.isDigit(c)) k = k * 10 + c - '0';

            else if (c == '[') {

                stack1.push(sb);

                stack2.push(k);

                sb = new StringBuffer();

                k = 0;

            }

            else if (c == ']') {

                int count = stack2.pop();

                String tmp = sb.toString();

                sb = stack1.pop();

                for (int i = 0; i < count; i++) sb.append(tmp);

            }

            else sb.append(c);

        }

        return sb.toString();

    }

巴特西

解码字符串 Decode String

最新文章

热门文章