[LeetCode] 394. Decode String

轉自LeetCode

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 kis 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".

<Solution>

看到有對稱形式，然後又可以內嵌

就可以往 stack 的方向去思考

想法如下

• 準備兩個 stack，一個存數字，一個存字串
• 遇到 ' [ '，就將目前的數字和字串 push 到 stack
• 遇到 ' ] '，就把當前的字串，重複 number stack 上 top 的次數，並接到 string stack 上的top

c++

	class Solution {
	public:
	string decodeString(string s) {
	string ansStr = "";
	int cnt = 0;
	stack<int> numStack;
	stack<string> strStack;
	for(int i = 0; i < s.length(); i++) {
	if(s[i] >= '0' && s[i] <= '9') {
	//> parse number
	cnt = cnt * 10 + (s[i] - '0');
	}
	else if(s[i] == '[') {
	//> push to stack
	numStack.push(cnt);
	strStack.push(ansStr);
	cnt = 0;
	ansStr.clear();
	}
	else if(s[i] == ']') {
	//> pop from stack and decode string
	int repeatNum = numStack.top();
	numStack.pop();
	while(repeatNum-- > 0) {
	strStack.top() += ansStr;
	}
	ansStr = strStack.top();
	strStack.pop();
	}
	else {
	//> add character to string
	ansStr += s[i];
	}
	}
	return ansStr;
	}
	};

view raw decodeString.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun decodeString(s: String): String {
	var ans = ""
	val numStack = mutableListOf<Int>()
	val strStack = mutableListOf<String>()
	var cnt = 0
	for(c in s) {
	when {
	c >= '0' && c <= '9' -> {
	cnt = cnt * 10 + (c-'0').toInt()
	}
	c == '[' -> {
	numStack.add(cnt)
	cnt = 0
	strStack.add(ans)
	ans = ""
	}
	c == ']' -> {
	var requireNum = numStack.last()
	numStack.removeAt(numStack.lastIndex)
	while(requireNum > 0) {
	strStack[strStack.lastIndex] = strStack.last() + ans
	--requireNum
	}
	ans = strStack.last()
	strStack.removeAt(strStack.lastIndex)
	}
	else -> {
	ans += c
	}
	}
	}
	return ans
	}
	}

view raw decode_string.kt hosted with ❤ by GitHub