作者:阳吉登 | 来源:互联网 | 2023-10-11 12:21
一、前言
标签:栈。
问题来源LeetCode 394 难度:中等。
问题链接:https://leetcode-cn.com/problems/decode-string/
二、题目
给定一个经过编码的字符串,返回它解码后的字符串。编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例 1:
输入:s = "3[a]2[bc]"
输出:"aaabcbc"
示例 2:
输入:s = "3[a2[c]]"
输出:"accaccacc"
示例 3:
输入:s = "2[abc]3[cd]ef"
输出:"abcabccdcdcdef"
示例 4:
输入:s = "abc3[cd]xyz"
输出:"abccdcdcdxyz"
三、思路
当看到括号,首先应该想到的就是用栈来解决问题。
四、编码实现
//==========================================================================
/*
* @file : 394_DecodeString.h
* @label : 栈
* @blogs : https://blog.csdn.net/nie2314550441/article/details/107522595
* @author : niebingyu
* @date : 2020/07/21
* @title : 394.字符串解码
* @purpose : 给定一个经过编码的字符串,返回它解码后的字符串。
* 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
* 你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
* 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
*
* 示例1:
* 输入:s = "3[a]2[bc]"
* 输出:"aaabcbc"
*
* 示例2:
* 输入:s = "3[a2[c]]"
* 输出:"accaccacc"
*
* 示例3:
* 输入:s = "2[abc]3[cd]ef"
* 输出:"abcabccdcdcdef"
*
* 示例 4:
* 输入:s = "abc3[cd]xyz"
* 输出:"abccdcdcdxyz"
*
* 来源:力扣(LeetCode)
* 难度:中等
* 链接:https://leetcode-cn.com/problems/decode-string/
*/
//==========================================================================
#pragma once
#include
#include
#include
#include
#include
using namespace std;#define NAMESPACE_DECODESTRING namespace NAME_DECODESTRING {
#define NAMESPACE_DECODESTRINGEND }
NAMESPACE_DECODESTRINGclass Solution
{
public:string decodeString(string s) {string res &#61; "";stack nums;stack strs;int num &#61; 0;int len &#61; s.size();for(int i &#61; 0; i &#61; &#39;0&#39; && s[i] <&#61; &#39;9&#39;)num &#61; num * 10 &#43; s[i] - &#39;0&#39;;else if((s[i] >&#61; &#39;a&#39; && s[i] <&#61; &#39;z&#39;) ||(s[i] >&#61; &#39;A&#39; && s[i] <&#61; &#39;Z&#39;))res &#61; res &#43; s[i];else if(s[i] &#61;&#61; &#39;[&#39;) {// 将‘[’前的数字压入nums栈内&#xff0c; 字母字符串压入strs栈内nums.push(num);num &#61; 0;strs.push(res); res &#61; "";}else {// 遇到‘]’时&#xff0c;操作与之相配的‘[’之间的字符&#xff0c;使用分配律int times &#61; nums.top();nums.pop();for(int j &#61; 0; j };以下为测试代码//
// 测试 用例 START
void test(const char* testName, string str, string expect)
{Solution s;string result &#61; s.decodeString(str);if (result &#61;&#61; expect)cout <}// 测试用例
void Test1()
{string str &#61; "3[a]2[bc]";string expect &#61; "aaabcbc";test("Test1()", str, expect);
}void Test2()
{string str &#61; "3[a2[c]]";string expect &#61; "accaccacc";test("Test2()", str, expect);
}void Test3()
{string str &#61; "2[abc]3[cd]ef";string expect &#61; "abcabccdcdcdef";test("Test3()", str, expect);
}void Test4()
{string str &#61; "abc3[cd]xyz";string expect &#61; "abccdcdcdxyz";test("Test4()", str, expect);
}
NAMESPACE_DECODESTRINGEND
// 测试 用例 END
//
void DecodeString_Test()
{cout <<"------ start 394.字符串解码 ------" <}
执行结果&#xff1a;