Catalogue of series articles
Force deduction hot question brushing record
preface
Make a little progress every day!!
1, Background
Source: force buckle
Link: https://leetcode-cn.com/problems/decode-string/
2, My thoughts
I first consider several cases. If the number is followed by [], it can be decoded directly. The problem is that its brackets are nested. What should I do.
The same is true for expression evaluation. It seems that the two are a little similar, so I can use stack fetching to solve the problem of bracket matching.
But what about strings inside nested parentheses?
Yes, use a local variable, but how can this local variable be associated with the last decoding, such as [3 [AA] 2 [BC]], this local variable is not easy to use.
Simply evaluate it directly as an expression, throw the parentheses together, and throw the others together. Just create two stacks, good.
Then, when there are parentheses matching, calculate the number * string in front of the matched parentheses (there must be a number in front of the left parenthesis, because the topic requires it), that is, decoding.
At first, I thought that the number k can only be 0-9. Later, I found that it can be greater than 9. I simply changed the stack to string (originally thought of char), but how can a string be turned into a number? Just write a function string yourself_ int(). OK, the code is as follows:
class Solution {
public:
int string_int(string s)
{
int sum=0;
for(int i=0;i<s.length();i++)
{
sum+=(s[i]-48)*pow(10,s.length()-i-1);
//cout<<sum<<endl;
}
return sum;
}
string decodeString(string s) {
stack<char> sta;//Used to hold brackets
stack<string> c_sta;//It is convenient for unification. I don't know if it will be wrong
string ans;//Record the final answer
for(int i=0;i<s.length();i++)
{
if(s[i]!='['&&s[i]!=']')
{
string m;
//Use while to finish the letters and numbers at one time to speed up the speed
while(s[i]>='a'&&s[i]<='z'||s[i]>='A'&&s[i]<='Z')
{
m=m+s[i++];
}
c_sta.push(m);//Put other characters that are not brackets in
m="";//Leave m blank
while(s[i]>='0'&&s[i]<='9')
{
m=m+s[i++];
}
c_sta.push(m);//Put other characters that are not brackets in
i--;//There is also a for loop outside that will + +, so we need to subtract
}
else if(s[i]=='[')
{
sta.push(s[i]);
}
else if(s[i]==']'&&sta.top()=='[')
{
sta.pop();
//If it matches, start the calculation
string mid_s="";//Declared as an empty string
string temp="";
//If it is not empty and is not a number, the string will be stacked. Because the brackets match, it means that [] must be a number before []
while(!c_sta.empty())
{
char c=c_sta.top()[0];
if(c<='9'&&c>='0')
break;
mid_s=c_sta.top()+mid_s;
c_sta.pop();
}
temp=mid_s;
for(int u=0;!c_sta.empty()&&u<string_int(c_sta.top())-1;u++)
mid_s+=temp;//temp times c_sta.top()[0]-48-1 pass mid_s itself
c_sta.pop();//Take the numbers out of the stack
c_sta.push(mid_s);//Push the result onto the stack
}
}
//All the characters in the character stack add up to the final answer
while(!c_sta.empty())
{
ans=c_sta.top()+ans;
c_sta.pop();
}
return ans;
}
};
3, Official thinking
1. Consistent with me
With a stack, she maintains it, but for numbers, go through it at one time, and for other characters, all go into the stack.
The right bracket comes and goes directly out of the stack, because there must be an left bracket, and the title says, legal string, so it must be so. Then, the string in the square brackets will come out of the stack. Just reverse it, and the next one in the left bracket must be a number (or that sentence, legal string). In this way, it can be calculated, and then press the calculation result into the stack.
The code is as follows:
class Solution {
public:
string getDigits(string &s, size_t &ptr) {
string ret = "";
while (isdigit(s[ptr])) {
ret.push_back(s[ptr++]);
}
return ret;
}
string getString(vector <string> &v) {
string ret;
for (const auto &s: v) {
ret += s;
}
return ret;
}
string decodeString(string s) {
vector <string> stk;
size_t ptr = 0;
while (ptr < s.size()) {
char cur = s[ptr];
if (isdigit(cur)) {
// Get a number and put it on the stack
string digits = getDigits(s, ptr);
stk.push_back(digits);
} else if (isalpha(cur) || cur == '[') {
// Get a letter and put it on the stack
stk.push_back(string(1, s[ptr++]));
} else {
++ptr;
vector <string> sub;
while (stk.back() != "[") {
sub.push_back(stk.back());
stk.pop_back();
}
reverse(sub.begin(), sub.end());
// Left bracket out of stack
stk.pop_back();
// At this time, the top of the stack is the number of times the string corresponding to the current sub should appear
int repTime = stoi(stk.back());
stk.pop_back();
string t, o = getString(sub);
// Construct string
while (repTime--) t += o;
// Stack the constructed string
stk.push_back(t);
}
}
return getString(stk);
}
};
Author: leetcode solution
Link: https://leetcode-cn.com/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-leetcode-solution/
Source: LeetCode
No wonder I ran out at the same time as it!!
2. Recursion
Nested brackets are repeated operations. Consider recursion.
There are two things about recursion. One is to consider repeated steps, and the other is to consider exits.
Repeat the steps: decode the correct string in the brackets, but the bracket itself is a new string waiting to be decoded, so you can call the recursive function. Encounter the letter itself, do not need to decode, calculate directly, encounter the brackets, recurse, calculate after the brackets, and recurse again.
Exit. If there is no nesting of brackets, the current exit is recursive.
class Solution {
public:
string src;
size_t ptr;
int getDigits() {
int ret = 0;
while (ptr < src.size() && isdigit(src[ptr])) {
ret = ret * 10 + src[ptr++] - '0';
}
return ret;
}
string getString() {
if (ptr == src.size() || src[ptr] == ']') {
// String -> EPS
return "";
}
char cur = src[ptr]; int repTime = 1;
string ret;
if (isdigit(cur)) {
// String -> Digits [ String ] String
// Parsing Digits
repTime = getDigits();
// Filter left parenthesis
++ptr;
// Parse String
string str = getString();
// Filter right parenthesis
++ptr;
// Construct string
while (repTime--) ret += str;
} else if (isalpha(cur)) {
// String -> Char String
// Parse Char
ret = string(1, src[ptr++]);
}
return ret + getString();
}
string decodeString(string s) {
src = s;
ptr = 0;
return getString();
}
};
Author: leetcode solution
Link: https://leetcode-cn.com/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-leetcode-solution/
Source: LeetCode
summary
Recursion is a little difficult to operate. Everything else is OK.
If you like, just order a praise!!!