394.Decode-String

394. Decode String

题目地址

https://leetcode.com/problems/decode-string/

题目描述

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

Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

代码

Approach #1 Two Stack

数字: countStack.push(count) [ : resStack.push(res), res = "" ]: pop, res = temp Else: res+=

class Solution {
  public String decodeString(String s) {
        String res = "";
    Stack<Integer> countStack = new Stack<>();
    Stack<Integer> resStack = new Stack<>();
    int idx = 0;
    while (idx < s.length()) {
      if (Character.isDigit(s.charAt(idx))) {
        int count = 0;
        while (Character.isDigit(s.charAt(idx))) {
          count = 10 * count + (s.charAt(idx) - '0');
          idx++;
        }
        countStack.push(count);
      }
      else if (s.charAt(idx) == '[') {
        resStack.push(res);
        res = "";
        idx++;
      }
      else if (s.charAt(idx) == ']') {
        StringBuilder temp = new StringBuilder(resStack.pop());
        int repeatTimes = countStack.pop();
        for (int i = 0; i < repeatTimes; i++) {
          temp.append(res);
        }
        res = temp.toString();
        idx++;
      }
      else {
        res += s.charAt(idx++);
      }
    }
    return res;
  }
}

Approach #2 DFS

使用一个全局pos记录递归位置

[ 开始递归， ] 返回结果

class Solution {
  private int pos = 0;
  public String decodeString(String s) {
    StringBuilder sb = new StringBuilder();
    String num = "";
    for (int i = pos; i < s.length(); i++) {
      // 1. 解析数字
           if (Character.isDigit(s.charAt(i))) {
        num += s.charAt(i);
      }
      // 2. '['， dfs递归，并记录pos
      else if (s.charAt(i) == '[') {
        pos = i + 1;
        String next = decodeString(s);
        for (int n = Integer.valueOf(num); n > 0; n--) {
          sb.append(next);
        }
        num = "";
        i = pos;
      } 
      // 3. retrun 结果
      else if (s.charAt(i) == ']') {
        pos = i; // 返回上一层会进入for循环 pos + 1
        return sb.toString();
      } 
      else {
        // 4. letter append
        sb.append(s.charAt(i));
      } 
    }

    return sb.toString();
  }
}

Approach #3 Queue

class Solution {
  public String decodeString(String s) {
    Deque<Character> queue = new LinkedList();
    for (char c: s.toCharArray()) {
      queue.offer(c);
    }
    return bfs(queue);
  }

  private String bfs(Deque<Character> queue) {
    StringBuilder sb = new StringBuilder();
    int num = 0;
    while (!queue.isEmpty()) {
      char c = queue.poll();
      // 1. digit
      if (Character.isDigit(c)) {
        num = num * 10 + c - '0';
      } 
      // 2. `[` 进入bfs递归
      else if (c == '[') {
        String sub = bfs(queue);
        for (int i = 0; i < num; i++) {
          sb.append(sub);
        }
        num = 0;
      }
      // 3. `]` break
      else if (c == ']') {
        break;
      }
      // 4. letter append
      else {
        sb.append(c);
      }
    }

    return sb.toString();
  }
}