牛客NC199 字符串解码【中等 递归，栈的思想 C++/Java/Go/PHP】

题目

题目链接：
https://www.nowcoder.com/practice/4e008fd863bb4681b54fb438bb859b92
相同题目：
https://www.lintcode.com/problem/575

思路

解法和基础计算器1，2,3类似,递归
1

参考答案C++

struct Info {
    string str;
    int stopindex;
    Info(string e, int c) : str(e), stopindex(c) {}
};

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串
     */
    string decodeString(string s) {
        //解法和基础计算器1，2,3类似,递归
        return process(s, 0).str;
    }

    Info process(string s, int idx) {
        string str;
        int cur = 0;
        while (idx < s.size() && s[idx] != ']') {
            char c = s[idx];
            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
                str += c;
                idx++;
            } else if (c >= '0' && c <= '9') {
                cur = cur * 10 + int(c - '0');
                idx++;
            } else { //遇到[  需要递归获取[...] 的结果
                Info info = process(s, idx + 1);
                str += getStr(info.str, cur);
                cur = 0;
                idx = info.stopindex + 1;
            }
        }

        return Info(str, idx);
    }

    string getStr(string s1, int count) {
        string ans;
        for (int i = 0; i < count; i++) {
            ans += s1;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串
     */
    public String decodeString (String s) {
        //解法和基础计算器1，2,3类似,递归
        return process(s, 0).ans;
    }

    public Info process(String s, int i) {
        StringBuilder ans = new StringBuilder();
        int cur = 0;
        while (i < s.length() && s.charAt(i) != ']') {
            char c = s.charAt(i);
            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
                ans.append(c);
                i++;
            } else if (c >= '0' && c <= '9') {
                cur = cur * 10 + c - '0';
                i++;
            } else { //遇到[
                Info next = process(s, i + 1);
                ans.append(getStr(next.ans, cur));
                cur = 0;
                i = next.stopIndex + 1;
            }
        }
        return new Info(ans.toString(), i);
    }

    public String getStr(String str, int count) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count ; i++) {
            sb.append(str);
        }

        return sb.toString();
    }


    static class Info {
        String ans;
        int stopIndex;
        public Info(String s, int e) {
            ans = s;
            stopIndex = e;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

参考答案Go

package main

import "bytes"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return string字符串
 */
func decodeString(s string) string {
	//本答案和解答基础计算器1,2,3的思路类似
	//递归。遇到字母，遇到数字，遇到[  三种情况
	return process(s, 0).str
}

func process(s string, idx int) Info {
	var buf bytes.Buffer
	cur := 0

	for idx < len(s) && s[idx] != ']' {
		c := s[idx]
		if (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') {
			buf.WriteString(string(c))
			idx++
		} else if c >= '0' && c <= '9' {
			cur = cur*10 + int(c-'0')
			idx++
		} else { //遇到[  递归去吧，我需要递归的结果
			info := process(s, idx+1)
			buf.WriteString(getStr(info.str, cur))
			cur = 0
			idx = info.stopindex + 1
		}
	}

	return Info{buf.String(), idx}
}

func getStr(str string, count int) string {
	var buf bytes.Buffer
	for i := 0; i < count; i++ {
		buf.WriteString(str)
	}

	return buf.String()
}

type Info struct {
	str       string
	stopindex int
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return string字符串
 */
function decodeString( $s )
{
     //本答案和解答基础计算器1,2,3的思路类似
    //递归。遇到字母，遇到数字，遇到[  三种情况

    return process($s,0)->str;
}

function process($s,$idx) {
    $str ='';
    $cur=0;
    while ($idx <strlen($s) && $s[$idx] !=']') {
        $c = $s[$idx];
        if(($c>='a' && $c<='z') ||($c>='A' && $c <='Z')){
            $str.=$c;
            $idx++;
        }else if($c>='0' && $c<='9'){
            $cur =$cur*10+intval($c-'0');
            $idx++;
        }else{ //遇到[ 了，递归获取[...] 中等的结果
            $info = process($s,$idx+1);
            $str.=(getStr($info->str,$cur));
            $cur =0;
            $idx = $info->stopindex+1;
        }
    }
    return new Info($str,$idx);
}

function getStr($s,$count){
    $str = '';
    for($i=0;$i<$count;$i++){
        $str.=$s;
    }
    return $str;
}

class Info{
    public $str;
    public $stopindex;
    public function __construct($a,$b){
        $this->str = $a;
        $this->stopindex = $b;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55