Decode String (M)

題目

Given an encoded string, return its 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].

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Example 4:

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

Constraints:

1 <= s.length <= 30
s consists of lowercase English letters, digits, and square brackets '[]'.
s is guaranteed to be a valid input.
All the integers in s are in the range [1, 300].

題意

按要求展開給定的字串，

思路

遞回：從左到右遍歷字串，如果是字母則直接加入的結果中；如果是數字，則先計算數字，再遞回展開'[ ]'中的字串，最后拼接起來，

代碼實作

Java

class Solution {
    public String decodeString(String s) {
        String ans = "";
        int i = 0;

        while (i < s.length()) {
            char c = s.charAt(i);
            if (c < '0' || c > '9') {
                ans += c;
                i++;
            } else {
              	// 計算數字
                int count = 0;
                while (s.charAt(i) != '[') {
                    count = count * 10 + s.charAt(i++) - '0';
                }
                i++;
                int start = i;
              
                // 找到匹配的']'
                int leftCount = 0;
                while (i < s.length()) {
                    if (s.charAt(i) == '[') {
                        leftCount++;
                    } else if (s.charAt(i) == ']' && leftCount > 0) {
                        leftCount--;
                    } else if (s.charAt(i) == ']' && leftCount == 0) {
                        break;
                    }
                    i++;
                }

                String tmp = decodeString(s.substring(start, i));
                ans += tmp.repeat(count);
                
                i++;
            }
        }

        return ans;
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/225046.html

標籤：其他

上一篇：（一）版本控制管理器之發展史

下一篇：0394. Decode String (M)