网站开发需求收集,大型门户网站建设 费用,中国企业500强最新排名2021,东莞公司想建网站LeetCode#xff1a;394. 字符串解码 本题容易想到用递归处理#xff0c;在写递归时主要是需要明确自己的递归函数的定义。 不过我们也可以利用括号匹配的方式使用栈进行处理。
1、递归
定义递归函数string GetString(string s,int i); 表示处理处理整个numbe…LeetCode394. 字符串解码 本题容易想到用递归处理在写递归时主要是需要明确自己的递归函数的定义。 不过我们也可以利用括号匹配的方式使用栈进行处理。
1、递归
定义递归函数string GetString(string s,int i); 表示处理处理整个number[letter]处理后i指向’]之后的一个元素当letter中有这样的结构时直接递归处理。 定义函数int GetNum(string s,int i); 在遇到数字时调用表示获取s中前缀的数
class Solution {
public:string decodeString(string s) {string target;int len s.size();for(int i 0; i len;){if(s[i] z s[i] a){target s[i ];}else{target GetString(s, i);}}return target;}
private:string GetString(string s,int i){//处理number[letter]处理后i指向]之后的一个元素int num GetNum(s, i);//获取重复次数 i;//忽略掉[string str;//获取字符串的前面字符位 3[aa2[cd]ff]while(s[i] ! ]){if(s[i] z s[i] a){str s[i ];}else{str GetString(s, i);}} i;//忽略掉]//重复子串string substr str;while(--num){str substr;}return str;}
private:int GetNum(string s,int i){int num 0;while(s[i] 0 s[i] 9){num * 10;num s[i ] -0;}return num;}
};2、栈操作
这里可以用不定长数组来模拟栈操作方便从栈底向栈顶遍历。 我们可以使用类似括号匹配的方法从左到右遍历字符串将字符串压入栈中遇到右括号]则说明一定会有一个左括号[匹配我们可以将这之间的内容弹栈并形成一个整体再从栈顶中拿出数字联合成一个串压入栈中以此类推直到所有的左右括号匹配完然后再链接所有串。
时间复杂度 O ( S ∣ s ∣ ) O(S |s|) O(S∣s∣)s是最终字符串长度|s|是原字符串的长度。 需要遍历原字符串一次并且每一个字符需要入栈一次每个字符要出栈一次字符串需要进行连接最终连接的长度取决于最终字符串长度。 空间复杂度 O ( S ) O(S) O(S)
class Solution {
public:string decodeString(string s) {vectorstring sta;for(auto i : s){if(i ]){string str;vectorstring temp;//获取[]中的字符串while(sta.back() ! [){temp.push_back(sta.back());sta.pop_back();}for(int j temp.size() - 1; j 0; -- j)str temp[j];//reverse(str.begin(), str.end());//翻转成正序sta.pop_back();//弹出[string digitStr;//获取数字串while(sta.size() 0 sta.back() 0 sta.back() 9){digitStr sta.back();sta.pop_back();}int num 0;//获取数字for(int j digitStr.size() - 1; j 0; -- j){num * 10;num digitStr[j] - 0;}//将number[letter]结合成一个串string substr str;while(--num) str substr;sta.emplace_back(str);}else sta.emplace_back(string() i);}string ans;for(auto i : sta)ans i;return ans;}
};注意这两者的区别 for(int j temp.size() - 1; j 0; -- j) str temp[j];reverse(str.begin(), str.end());//翻转成正序 前者并不改变栈中字符串内部顺序而是改变栈中字符串之间的相对顺序后者会改变栈中字符串的内部顺序
