leetcode394-字符串解码

原题

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

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a2[4] 的输入。

示例:

s = “3[a]2[bc]”, 返回 “aaabcbc”.
s = “3[a2[c]]”, 返回 “accaccacc”.
s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.

解法

思想

DFS,只处理字符串中不包含括号的,遇到带括号的将其分解。

代码

class Solution {
    public String decodeString(String s) {
        return multify(1,s);
    }
    public String multify(int repeat,String s){
        StringBuilder sb = new StringBuilder();
        //字符串中不带括号
        if(s.indexOf('[') == -1){
            for(int i = 0;i<repeat;i++){
                sb.append(s);
            }
            return sb.toString();
        }else{
            //未匹配括号的个数
            int count = 0;
            //第一个数字出现的index
            int firstNumberIndex = 0;
            //第一个左括号出现的index
            int firstLeftIndex = 0;
            boolean firstNumberHasShown = false;
            for(int i = 0;i<s.length();i++){
                //如果是数字记录第一个数字出现的index
                if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
                    if(firstNumberHasShown == false){  
                        firstNumberIndex = i;
                        firstNumberHasShown = true;
                    }
                }
                //如果是左括号记录第一个左括号出现的index
                else if(s.charAt(i) == '['){
                    if(count == 0)
                        firstLeftIndex = i;
                    count ++;
                }
                //如果是右括号则未匹配的左括号数量减一,如果全部匹配完则把repeat和substring递归处理。
                else if(s.charAt(i) == ']'){
                    count --;
                    if(count == 0) {
                        firstNumberHasShown = false;
                        int repeatNum = Integer.valueOf(s.substring(firstNumberIndex,firstLeftIndex));
                        String subString = s.substring(firstLeftIndex+1,i);
                        sb.append(multify(repeatNum,subString));
                    }   
                }
                else if(count==0){
                    sb.append(s.charAt(i));
                }
            }
        }
        return multify(repeat,sb.toString());
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode394-%e5%ad%97%e7%ac%a6%e4%b8%b2%e8%a7%a3%e7%a0%81/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月12日
下一篇 2019年12月14日

相关推荐

  • leetcode23-合并K个排序链表

    原题 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->…

    算法 2020年2月4日
    0170
  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0210
  • leetcode103-二叉树的锯齿形层次遍历

    原题 给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 例如:给定二叉树: [3,9,20,null,nul…

    算法 2020年1月25日
    060
  • leetcode295-数据流的中位数

    原题 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.…

    算法 2020年2月12日
    0120
  • leetcode27-移除元素

    原题 给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(…

    算法 2019年11月20日
    080
  • 剑指offer03-数组中重复的数字

    原题(来源Leetcode) 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,…

    算法 2020年3月13日
    0140
  • leetcode367-有效的完全平方数

    原题 给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。 说明: 不要使用任何内置的库函数,如  sqrt。 示例1: …

    算法 2020年1月5日
    0150
  • 蓝桥杯试题-大小写转换

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   输入一个字符串,将大写字符变成小写、小写变成大写,然后输出 输入格式 acbAB 输出格式 ACBab …

    算法 2020年2月29日
    060
  • leetcode217-存在重复元素

    原题 给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。 示例1: 输入: [1,2,3…

    算法 2019年12月18日
    080
  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, b…

    算法 2019年11月18日
    090

发表回复

登录后才能评论