Go?Java算法之字符串怎么解碼

這篇文章主要講解了“Go Java算法之字符串怎么解碼”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Go Java算法之字符串怎么解碼”吧！

字符串解碼

給定一個(gè)經(jīng)過編碼的字符串，返回它解碼后的字符串。

編碼規(guī)則為: k[encoded_string]，表示其中方括號內(nèi)部的 encoded_string 正重復(fù) k 次。注意 k 保證為正整數(shù)。

你可以認(rèn)為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。

此外，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復(fù)的次數(shù) k ，例如不會(huì)出現(xiàn)像 3a 或 2[4] 的輸入。

• 示例 1：

輸入：s = "3[a]2[bc]"

輸出："aaabcbc"

• 示例 2：

輸入：s = "3[a2[c]]"

輸出："accaccacc"

• 示例 3：

輸入：s = "2[abc]3[cd]ef"

輸出："abcabccdcdcdef"

• 示例 4：

輸入：s = "abc3[cd]xyz"

輸出："abccdcdcdxyz"

方法一：棧（Java）

看到括號的匹配，首先應(yīng)該想到的就是用棧來解決問題。

首先因?yàn)閿?shù)字可能不止一位，為了更清晰方便可以使用兩個(gè)棧，一個(gè)存儲(chǔ)數(shù)字，一個(gè)存字符。當(dāng)遇到除了]外的字符先入字符棧，遇到數(shù)字則將完整的數(shù)字轉(zhuǎn)換后入數(shù)字棧，而當(dāng)遇到]時(shí)將字符棧中彈出直到[為止的字符構(gòu)成一個(gè)臨時(shí)字符串，并彈出數(shù)字棧頂元素，將臨時(shí)字符串重復(fù)該數(shù)字次數(shù)后重新入字符棧。

當(dāng)從左到右遍歷完原始串后棧中元素就是最后的答案

具體方法思路：遍歷這個(gè)棧

• 如果當(dāng)前的字符為數(shù)位，解析出一個(gè)數(shù)字（連續(xù)的多個(gè)數(shù)位）并進(jìn)棧

• 如果當(dāng)前的字符為字母或者左括號，直接進(jìn)棧

• 如果當(dāng)前的字符為右括號，開始出棧，一直到左括號出棧，出棧序列反轉(zhuǎn)后拼接成一個(gè)字符串，此時(shí)取出棧頂?shù)臄?shù)字，就是這個(gè)字符串應(yīng)該出現(xiàn)的次數(shù)，我們根據(jù)這個(gè)次數(shù)和字符串構(gòu)造出新的字符串并進(jìn)棧

class Solution {
    int ptr;
    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;
        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                // 獲取一個(gè)數(shù)字并進(jìn)棧
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == '[') {
                // 獲取一個(gè)字母并進(jìn)棧
                stk.addLast(String.valueOf(s.charAt(ptr++))); 
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                // 左括號出棧
                stk.removeLast();
                // 此時(shí)棧頂為當(dāng)前 sub 對應(yīng)的字符串應(yīng)該出現(xiàn)的次數(shù)
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                // 構(gòu)造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 將構(gòu)造好的字符串入棧
                stk.addLast(t.toString());
            }
        }
        return getString(stk);
    }
    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }
    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}

時(shí)間復(fù)雜度：O（N）

空間復(fù)雜度：O（N）

方法二：遞歸（Go）

上文提到的方法為使用棧，因此我們可以隨之想到通過使用遞歸的方式來完成。具體遞歸的思路，請看下文內(nèi)容。

需要解決多個(gè)括號之間的嵌套問題。也就是重疊子問題。使用?；蜻f歸的解題方式都是可以。

• 1、首先標(biāo)識右括號結(jié)束的位置。

• 2、遇到左括號，i+1傳遞給下一次

• 3、結(jié)束左括號的運(yùn)行將乘積次數(shù)置零，i=上一次右括號接觸的位置。繼續(xù)將右括號外面剩余的字符加完。

具體思路：從左向右解析字符串：

• 如果當(dāng)前位置為數(shù)字位，那么后面一定包含一個(gè)用方括號表示的字符串，即屬于這種情況：k[...]：

• 我們可以先解析出一個(gè)數(shù)字，然后解析到了左括號，遞歸向下解析后面的內(nèi)容，遇到對應(yīng)的右括號就返回，此時(shí)我們可以根據(jù)解析出的數(shù)字 x 解析出的括號里的字符串 s' 構(gòu)造出一個(gè)新的字符串 X * s′

• 我們把 k[...] 解析結(jié)束后，再次調(diào)用遞歸函數(shù)，解析右括號右邊的內(nèi)容

• 如果當(dāng)前位置是字母位，那么我們直接解析當(dāng)前這個(gè)字母，然后遞歸向下解析這個(gè)字母后面的內(nèi)容。

func decodeString(s string) string {
	var decode func(start int) (string, int)
	decode = func(start int) (str string, end int) {
		num:= 0
		for i := start; i < len(s); i++ {
			if isNumber(s[i]) {
				num = num*10 + int(s[i]-'0')
			} else if isLetter(s[i]) {
				str += string(s[i])
			} else if s[i] == '[' {
				item, index := decode(i + 1)
				for num != 0 {
					str += item
					num--
				}
				i = index
			} else if s[i] == ']' {
				end = i
				break
			}
		}
		return str, end
	}
	res, _ := decode(0)
	return res
}
func isLetter(u uint8) bool {
	return u >= 'A' && u <= 'Z' || u >= 'a' && u <= 'z'
}
func isNumber(u uint8) bool {
	return u >= '0' && u <= '9'
}

時(shí)間復(fù)雜度：O（N）

空間復(fù)雜度：O（N）

感謝各位的閱讀，以上就是“Go Java算法之字符串怎么解碼”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Go Java算法之字符串怎么解碼這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！