Java教程

Leetcode--Java--394. 字符串解码

本文主要是介绍Leetcode--Java--394. 字符串解码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

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

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

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

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

样例描述

示例 1:

输入:s = "3[a]2[bc]"
输出:"aaabcbc"
示例 2:

输入:s = "3[a2[c]]"
输出:"accaccacc"

思路

递归

  1. 碰到数字,就递归后面的[]中的部分,然后拼接起来为结果
  2. Java如果s和u放在参数传递会超时,得设置为全局变量
  3. 碰到[]括号直接过滤,记得在碰到]的时候将结果返回上一层,避免重复
    在这里插入图片描述

代码

class Solution {
    char c[];
    int u;
    int n;
    public String decodeString(String s) {
        c = s.toCharArray();
        u = 0;
        n = c.length;
        return dfs();
    }
    public String dfs() {
        String res = "";
        while (u < n) {
            if (c[u] >= '0' && c[u] <= '9') {
                int num = 0, j = u;
                while (j < n && (c[j] >= '0' && c[j] <= '9')) {
                    num = num * 10 + (c[j ++] - '0');
                }
                u = j;
                //递归得到后面的结果
                String s = dfs();
                //按照次数拼接k次
                for (int i = 0; i < num; i ++ ) {
                    res += s;
                }
            }
              else   if (Character.isLetter(c[u])) {
                        res += c[u];
                        //移动u
                        u ++;
                    } else if (c[u] == '['){
                        u ++;
                    } else if (c[u] == ']') {
                        u ++;
                        //这里一定要返回,到达右括号,说明某一层递归达到结果 返回给上一层用
                        return res;
                    }
         }
        return res;
    }
}
这篇关于Leetcode--Java--394. 字符串解码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!