leetcode394. Decode String

题目：题目链接

思路：好家伙，第一反应是递归。其实我们可以把他看成：
$$s=s1k[s2]s3$$
其中k是数字，s,s1,s2,s3是字符串。另外，s2也可以是s。

方法一 递归

那么我们知道了我们处理s时，只需要在s2进行递归调用就可以了。那么你可能肯定会做了吧。不会做也没关系，我也不会。哈哈哈哈。实际递归编写还是有难度的啊，我参考了大神的代码，我写不出来。。。。看代码吧：

class Solution {
public:bool isDigit(char c) {return c >= '0' && c <= '9';}bool isAlpha(char c) {return c >= 'a' && c <= 'z';}int i = 0;string slove(string s) {// s = s1k[s2]s3string res = "";for (; i < s.size(); ++i) {if (isAlpha(s[i])) res += s[i];//如果是字母就直接加，开始是s1,经过了k[s2]，加的就是s3了。else if (s[i] == ']') break;//右括号表示该层[s2]结束，可以返回上一层。else {//数字加[]int cnt = 0;//记录重复次数while (isDigit(s[i])) cnt = cnt * 10 + s[i++] - '0';//k++i;//此时s[i]='['string tmp = slove(s, i);//递归调用while (cnt-- > 0) res += tmp;//讲k*s2加入到res}}return res;}string decodeString(string s) {return slove(s);}
};

递归调用的时候，有一个数应该是全局变量，就是s的下标。
然后看注释吧。

方法二 栈

能用递归，那就能用栈嘛，因为递归在程序中不就是以栈的形式嘛。根据方法一，可以花亿点点脑筋写出栈的版本。
这里可以使用一个栈也可以使用2个，差别不大。一个保存数字，一个保存字符串。
此外，我们需要清楚一点，对于s1k[s2]s3来说，字符串的栈里面存放的是s1,而不是s2。
这点需要注意，看代码后也能发现。我们字符串栈保存的是[]之前的字符串。
看待代码吧：

class Solution {
public:bool isDigit(char c) {return c >= '0' && c <= '9';}bool isAlpha(char c) {return c >= 'a' && c <= 'z';}string slove(string s) {stack<int>s_num;//存数字stack<string>s_str;//存字符串string ans = "";int cnt = 0;for (int i = 0; i < s.size(); ++i) {while (isDigit(s[i])) cnt = cnt * 10 + s[i++] - '0';//记录重复个数if (isAlpha(s[i])) ans += s[i];//是字母就直接加到答案后面else if (s[i] == '[') {//进栈操作，将cnt和ans进栈表示这是在[string]前，组成公式 ans += cnt*[string]s_num.push(cnt);s_str.push(ans);cnt = 0;ans = "";}else {//碰到']'，执行出栈操作。int k = s_num.top(); s_num.pop();//拿出k[s2]，那么需要同时弹出k和now_ans,注意ans可没有进栈，ans是s2string now_ans = s_str.top(); s_str.pop();//根据s1k[s2],    now_ans是s1,  ans是s2。for (int j = 0; j < k; ++j) now_ans += ans;//s1 += k*s2ans = now_ans;//更新当前字符串，因为s1k[s2]s3的情况，所以后面还需有加入s3。}}return ans;}string decodeString(string s) {return slove(s);}
};

非常抱歉，兄弟们。这题我也不会写，我也是看网上的代码然后理解的。所以我代码中的注释，最好是在你敲代码时卡壳了可以看看，没准有收获。如果根本不会的话，还是建议去看大神的博客。对不住了，兄弟。
加油加油加油加加油加油加油加油！！！！！！！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！