Go Java 算法之字符串解碼示例詳解

Posted on by

字符串解碼

給定一個經過編碼的字符串，返回它解碼後的字符串。

編碼規則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正重復 k 次。註意 k 保證為正整數。

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

此外，你可以認為原始數據不包含數字，所有的數字隻表示重復的次數 k ，例如不會出現像 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）

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

首先因為數字可能不止一位，為瞭更清晰方便可以使用兩個棧，一個存儲數字，一個存字符。當遇到除瞭]外的字符先入字符棧，遇到數字則將完整的數字轉換後入數字棧，而當遇到]時將字符棧中彈出直到[為止的字符構成一個臨時字符串，並彈出數字棧頂元素，將臨時字符串重復該數字次數後重新入字符棧。

當從左到右遍歷完原始串後棧中元素就是最後的答案

具體方法思路：遍歷這個棧

  • 如果當前的字符為數位，解析出一個數字（連續的多個數位）並進棧
  • 如果當前的字符為字母或者左括號，直接進棧
  • 如果當前的字符為右括號，開始出棧，一直到左括號出棧，出棧序列反轉後拼接成一個字符串，此時取出棧頂的數字，就是這個字符串應該出現的次數，我們根據這個次數和字符串構造出新的字符串並進棧
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)) {
                // 獲取一個數字並進棧
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == '[') {
                // 獲取一個字母並進棧
                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();
                // 此時棧頂為當前 sub 對應的字符串應該出現的次數
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                // 構造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 將構造好的字符串入棧
                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();
    }
}

時間復雜度：O（N）

空間復雜度：O（N）

方法二：遞歸（Go）

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

需要解決多個括號之間的嵌套問題。也就是重疊子問題。使用棧或遞歸的解題方式都是可以。

  • 1、首先標識右括號結束的位置。
  • 2、遇到左括號，i+1傳遞給下一次
  • 3、結束左括號的運行將乘積次數置零，i=上一次右括號接觸的位置。繼續將右括號外面剩餘的字符加完。

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

  • 如果當前位置為數字位，那麼後面一定包含一個用方括號表示的字符串，即屬於這種情況：k[…]：
  • 我們可以先解析出一個數字，然後解析到瞭左括號，遞歸向下解析後面的內容，遇到對應的右括號就返回，此時我們可以根據解析出的數字 x 解析出的括號裡的字符串 s' 構造出一個新的字符串 X * s′
  • 我們把 k[…] 解析結束後，再次調用遞歸函數，解析右括號右邊的內容
  • 如果當前位置是字母位，那麼我們直接解析當前這個字母，然後遞歸向下解析這個字母後面的內容。
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'
}

時間復雜度：O（N）

空間復雜度：O（N）

以上就是Go Java 算法之字符串解碼示例詳解的詳細內容，更多關於Go Java算法之字符串解碼的資料請關註WalkonNet其它相關文章！

推薦閱讀：