leetcode解题: Decode String (394)

发表于 | 分类于

Given an encoded string, return it’s 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:

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

解法1： 递归

主要的想法就是， 每一个数字后面一定跟着一个左括号。 而左括号里面的东西是另外一个decode的过程，一个decode结束的标志是要么string结束了，或者是遇到了右括号（[),
要注意的是,为了要不停的往前扫描,我们在递归函数返回的时候需要记录当前扫描到的位置. 可以用辅助class解决,在c++里也可以用引用解决这个问题.
C++

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
class Solution {
public:
	string decodeString(string s) {
		int pos = 0;
		string res = decode(s, pos);
		return res;
	}
	string decode(string s, int& pos) {
		string res = "";
		while (pos < s.size() && s[pos] != ']') {
			if (!isdigit(s[pos])) {
				res += s[pos];
			} else {
				int start = pos;
				while (pos < s.size() && isdigit(s[pos])) {
					pos++;
				}
				int number = stoi(s.substr(start, pos));
				pos++;	// skip the [
				string next = decode(s, pos);
				pos++;	// since decode stops at ] or at the end of string, we need to skip ]
				for (int i = 0; i < number; ++i) {
					res += next;
				}
			}
		}
		return res;
	}	 
};

Java

1

解法2: Stack

用递归的算法如果要用iteration的办法解决一般会用到Stack. 基本的思路是用两个stack分别记录数字和字符, 当遇到”]”时使用当前栈顶的字母和数字来进行decode, 然后decode的结果要存入字母的栈顶.
最后的结果要么是当前的字符串, 要么是栈顶的字符串.
C++

lang: cpp
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
34
class Solution {
public:
	string decodeString(string s) {
		stack<int> numbers;
		stack<string> decoded;
		string t;	// 记录在遇到"["之前的string
		int number = 0;	
		for (int i = 0; i < s.size(); ++i) {
			if (isdigit(s[i])) {
				number = number * 10 + s[i] - '0';
			} else if (s[i] == '[') {
				numbers.push(number);
				number = 0;
				decoded.push(t);	// 把当前所记录到的string存入栈中
				t = "";
			} else if (s[i] == ']') {
				int rep = numbers.top();
				numbers.pop();
				for (int j = 0; j < rep; ++j) {
					decoded.top() += t;	// t记录了当前扫描到还没有decode的string
				}
				t = decoded.top();	
				decoded.pop();	
			} else {
				t += s[i];
			}
		}
		return decoded.empty()? t : decoded.top();
	}
};