字符串解码

原题链接

使用的方法

递归

• Character.isLetter() 方法用于判断指定的字符是否为字母。

• StringBuilder.append() 方法用于将指定的字符串追加到此字符序列。

• StringBuilder.toString() 方法用于将此字符序列转换为一个字符串。

• StringBuilder() 构造方法用于创建一个空的 StringBuilder 对象。

• StringBuilder.repeat() 方法用于创建一个新的字符串，该字符串是通过重复当前字符串指定次数得到的。

• StringBuilder.repeat(String str, int count) 方法用于创建一个新的字符串，该字符串是通过重复指定字符串指定次数得到的。

• String.substring() 方法用于返回一个新的字符串，它是此字符串的一个子字符串。

• String.charAt() 方法用于返回指定索引处的字符。

• String.isEmpty() 方法用于判断字符串是否为空。

• Integer.parseInt() 方法用于将字符串参数解析为一个整数。

解题思路

• 给定一个经过编码的字符串，返回它解码后的字符串。编码规则为：k[encoded_string]，其中 encoded_string 是被重复 k 次的字符串。注意 k 是一个正整数。
• 我们可以使用递归来解码字符串。递归的基本思想是将问题分解成更小的子问题，并通过调用自身来解决这些子问题。在这个问题中，我们可以通过递归地处理字符串来解码它。
• 首先，我们检查字符串是否为空，如果是空字符串，我们直接返回它。
• 接下来，我们检查字符串的第一个字符是否是字母。如果是字母，我们将其与递归调用剩余字符串的结果连接起来，并返回这个结果。
• 如果第一个字符是数字，我们需要找到对应的括号来确定要重复的字符串。我们使用一个变量 balance 来跟踪括号的平衡状态。
• 当我们遇到一个左括号时，我们将 balance 增加1，当我们遇到一个右括号时，我们将 balance 减少1。
• 当 balance 为0时，我们找到了完整的括号。
• 我们使用 Integer.parseInt() 方法将数字部分转换为整数 k，并使用递归调用来解码括号内的字符串。
• 最后，我们使用 StringBuilder 来构建最终的解码字符串。我们重复解码后的字符串 t k 次，并将其与递归调用剩余字符串的结果连接起来，最终返回这个结果。

代码实现

class Solution {
    public String decodeString(String s) {
        if(s.isEmpty())
            return s;
        // 如果第一个为字母
        if(Character.isLetter(s.charAt(0)))
            // 分离s[0],递归剩下的
            return s.charAt(0) + decodeString(s.substring(1));
        // 如果为数字，找括号
        int i = s.indexOf('[');// 记录左括号位置
        int balance = 1; // 记录括号个数:左括号加，右括号减
        for(int j=i+1; ;j++){
            char c = s.charAt(j);
            if(c == '[')
                balance++;
            else if(c == ']'){
                balance--;
                if(balance == 0){ // 为0则说明找到完整括号
                    int k = Integer.parseInt(s.substring(0,i)); // 记录重复个数
                    String t = decodeString(s.substring(i+1,j));
                    return new StringBuilder()
                        .repeat(t,k)
                        .append(decodeString(s.substring(j+1)))
                        .toString();
                }
            }
        }
    }
}