解码一个递归编码为count后跟子字符串的字符串, LeetCode — 394. Decode String

布满荆棘的人生 2023-06-20 09:06 88阅读 0赞

# 解码一个递归编码为count后跟子字符串的字符串 #

给出了一个已编码的字符串，任务是对其进行解码。字符串编码的模式如下。

<count> [sub_str] ==>子字符串'sub_str' 
                          出现计数时间。

**例子：**

输入：str [] =“ 1 [b]”
    输出：b
    
    输入：str [] =“ 2 [ab]”
    输出：abab
    
    输入：str [] =“ 2 [a2 [b]]”
    输出：abbabb
    
    输入：str [] =“ 3 [b2 [ca]]”
    输出：bcacabcacabcaca

## [推荐：在继续解决方案之前，请先在“ ***实践*** ” 上解决它。][Link 1] ##

此题有两种解法：

解法（一） 用堆栈，一个字母堆栈，一个数字堆栈

解法（二） 用递归， 递归方法，以dfs递归处理。

参考： [https://programmer.help/blogs/leetcode-394-string-decode-string.html][https_programmer.help_blogs_leetcode-394-string-decode-string.html]

现以堆栈的方法举例，进行分析：

想法是使用两个堆栈，一个用于整数，另一个用于字符。

此方法同时可以参考视频讲解：[https://www.youtube.com/watch?v=0iQqj5egK9k][https_www.youtube.com_watch_v_0iQqj5egK9k]    【此视频“科学上网”才能访问的。你懂的】

现在，遍历字符串，

1.  每当我们遇到任何数字时，都将其压入整数堆栈，如果是字母（a至z）或方括号（'\['），则将其压入字符堆栈。
2.  每当遇到任何尖括号（'\]'）时，请从字符堆栈中弹出字符，直到在字符堆栈中找不到开括号（'\['）。另外，从整数堆栈中弹出顶部元素，例如n。现在，使一个字符串重复弹出的字符n次。现在，将字符串的所有字符压入堆栈。

![format_png][]

以下是此方法的实现：

// Java program to decode a string recursively 
    // encoded as count followed substring 
      
    import java.util.Stack; 
      
    class Test 
    { 
        // Returns decoded string for 'str' 
        static String decode(String str) 
        { 
            Stack<Integer> integerstack = new Stack<>(); 
            Stack<Character> stringstack = new Stack<>(); 
            String temp = "", result = ""; 
           
            // Traversing the string 
            for (int i = 0; i < str.length(); i++) 
            { 
                int count = 0; 
           
                // If number, convert it into number 
                // and push it into integerstack. 
                if (Character.isDigit(str.charAt(i))) 
                { 
                    while (Character.isDigit(str.charAt(i))) 
                    { 
                        count = count * 10 + str.charAt(i) - '0'; 
                        i++; 
                    } 
           
                    i--; 
                    integerstack.push(count); 
                } 
           
                // If closing bracket ']', pop elemment until 
                // '[' opening bracket is not found in the 
                // character stack. 
                else if (str.charAt(i) == ']') 
                { 
                    temp = ""; 
                    count = 0; 
           
                    if (!integerstack.isEmpty()) 
                    { 
                        count = integerstack.peek(); 
                        integerstack.pop(); 
                    } 
           
                    while (!stringstack.isEmpty() && stringstack.peek()!='[' ) 
                    { 
                        temp = stringstack.peek() + temp; 
                        stringstack.pop(); 
                    } 
           
                    if (!stringstack.empty() && stringstack.peek() == '[') 
                        stringstack.pop(); 
           
                    // Repeating the popped string 'temo' count 
                    // number of times. 
                    for (int j = 0; j < count; j++) 
                        result = result + temp; 
           
                    // Push it in the character stack. 
                    for (int j = 0; j < result.length(); j++) 
                        stringstack.push(result.charAt(j)); 
           
                    result = ""; 
                } 
           
                // If '[' opening bracket, push it into character stack. 
                else if (str.charAt(i) == '[') 
                { 
                    if (Character.isDigit(str.charAt(i-1))) 
                        stringstack.push(str.charAt(i)); 
           
                    else
                    { 
                        stringstack.push(str.charAt(i)); 
                        integerstack.push(1); 
                    } 
                } 
           
                else
                    stringstack.push(str.charAt(i)); 
            } 
           
            // Pop all the elmenet, make a string and return. 
            while (!stringstack.isEmpty()) 
            { 
                result = stringstack.peek() + result; 
                stringstack.pop(); 
            } 
           
            return result; 
        } 
      
        // Driver method 
        public static void main(String args[]) 
        { 
            String str = "3[b2[ca]]"; 
            System.out.println(decode(str)); 
        } 
    }

[Link 1]: https://practice.geeksforgeeks.org/problems/decode-the-string/0
[https_programmer.help_blogs_leetcode-394-string-decode-string.html]: https://programmer.help/blogs/leetcode-394-string-decode-string.html
[https_www.youtube.com_watch_v_0iQqj5egK9k]: https://www.youtube.com/watch?v=0iQqj5egK9k
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tZWRpYS5nZWVrc2ZvcmdlZWtzLm9yZy93cC1jb250ZW50L3VwbG9hZHMvRGVjb2RlLnBuZw?x-oss-process=image/format,png