leetcode394字符串解码(回溯|栈)「建议收藏」

leetcode394字符串解码(回溯|栈)「建议收藏」给定一个经过编码的字符串,返回它解码后的字符串。编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。示例 1:输入:s = “3[a]2[bc]”输出:”aaabcbc”示例 2:输入:s =

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: 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"

题解
注意可能会出来[[]]嵌套的情况

  1. 回溯
class Solution { 
   
public:
    stringstream ss;
    string chartostring(char a){ 
   
        string t = "";
        t.append(1,a);
        return t;
    }
    string dfs(int l,int r,string &s){ 
   
        if(l == r)return chartostring(s[l]);
        if(l > r)return "";
        string t = "";
        if(s[l] >= 'a' && s[l] <= 'z'){ 
   
            t.append(1,s[l]);
            return t += dfs(l + 1,r,s);
        }
        else{ 
   
            int k = l;
            while(k < s.size() && s[k] >= '0' && s[k] <= '9')k ++;
            ss.clear();
            ss << s.substr(l,k - l);
            int num;
            ss >> num;
            int rr = k + 1,cnt = 1;
            while(cnt != 0){ 
   
                if(s[rr] == '[')cnt ++;
                else if(s[rr] == ']')cnt --;
                rr ++;
            }
            rr --;
            string tt = dfs(k + 1,rr - 1,s);
            for(int i = 0;i < num;i ++)t.append(tt);
            t += dfs(rr + 1,r,s);
        }
        cout<<t<<endl;
        return t;
    }
    string decodeString(string s) { 
   
        string res = dfs(0,s.size() - 1,s);
        return res;
    }
};
class Solution { 
   
public:
    string chartostring(char x){ 
   
        string t = "";
        t.append(1,x);
        return t;
    }
    bool isalpha(char x){ 
   
        return x >= 'a' && x <= 'z';
    }
    bool isnum(char x){ 
   
        return x >= '0' && x <= '9';
    }
    string decodeString(string s) { 
   
        stack<string>stk;
        stringstream ss;
        string res = "";
        int num = 0;
        for(int i = 0;i < s.size();i ++){ 
   
            if(isalpha(s[i]) || s[i] == '['){ 
   
                stk.push(chartostring(s[i]));
            }
            else if(isnum(s[i])){ 
   
                int j = i;
                while(j < s.size() && isnum(s[j]))j ++;
                stk.push(s.substr(i,j - i));
                i = j - 1;
            }else{ 
   
                string t = "";
                while(stk.top() != "["){ 
   
                    t.insert(0,stk.top());
                    stk.pop();
                }
                stk.pop();
                ss.clear();
                ss << stk.top();
                ss >> num;
                stk.pop();
                string tt = "";
                for(int i = 0;i < num;i ++){ 
   
                    tt.insert(0,t);
                }
                stk.push(tt);
            }
        }
        while(!stk.empty()){ 
   
            res.insert(0,stk.top());
            stk.pop();
        }
        return res;
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168712.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • mysql两列字段 分组去重统计_mysql组合字段去重

    mysql两列字段 分组去重统计_mysql组合字段去重直接了当上SQL SELECT a.字段1, a.字段2, b.字段1, COUNT(DISTINCT a.字段1),COUNT(DISTINCT b.字段1) FROM xs_highway_transport_log a LEFT JOIN b表 b ON b.id = a.main GROUP BY a.字段1 ,b.字段1// 这行为分组直接这样 即可实现 多字段去重情况。同时可以配合having过滤分组,也可以在 分组

  • c++入门教程–-18指针

    c++入门教程–-18指针

  • k8sV1.18.0版本一键部署脚本(全部代码在下方)

    k8sV1.18.0版本一键部署脚本(全部代码在下方)

  • Elasticsearch数据库

    Elasticsearch数据库1、什么是Elasticsearch1、概念以及特点        1、Elasticsearch和MongoDB/Redis/Memcache一样,是非关系型数据库。是一个接近实时的搜索平台,从索引这个文档到这个文档能够被搜索到只有一个轻微的延迟,企业应用定位:采用RestfulAPI标准的可扩展和高可用的实时数据分析的全文搜索工具。   2、可拓展:支持一主多从且扩容简易,只要clust…

  • 自己动手写游戏:Flappy Bird

    一、关于FlappyBird《FlappyBird》是由来自越南的独立游戏开发者DongNguyen所开发的作品,游戏中玩家必须控制一只小鸟,跨越由各种不同长度水管所组成的障碍,而这只鸟其实是

    2021年12月19日
  • linux ioctl函数详解,ioctl函数详解「建议收藏」

    linux ioctl函数详解,ioctl函数详解「建议收藏」1.介绍Linux网络程序与内核交互的方法是通过ioctl来实现的,ioctl与网络协议栈进行交互,可得到网络接口的信息,网卡设备的映射属性和配置网络接口.并且还能够查看,修改,删除ARP高速缓存的信息,所以,我们有必要了解一下ioctl函数的具体实现.2.相关结构体与相关函数#includeintioctl(intd,intrequest,….);参数:d-文件描述符,这里是对网络套…

    2022年10月18日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号