문자열 디코딩에 Go Java 알고리즘을 사용하는 방법은 무엇입니까?

문자열 디코딩

인코딩된 문자열이 주어지면 디코딩된 문자열을 반환합니다.

인코딩 규칙은 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"

방법 1: 스택(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 == &#39;[&#39;) {
                // 获取一个字母并进栈
                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)

방법 2: 재귀(Go)

위에서 언급한 방법은 스택을 사용합니다. 그러면 우리는 그것을 완성하기 위해 재귀를 사용하는 것을 생각할 수 있습니다. 구체적인 재귀 아이디어는 아래를 참조하세요.

여러 괄호 사이의 중첩 문제를 해결해야 합니다. 즉, 하위 문제가 겹치는 것입니다. 스택이나 재귀를 사용하여 문제를 해결할 수 있습니다.

• 1. 먼저 오른쪽 괄호가 끝나는 위치를 확인하세요.

• 2. 왼쪽 괄호를 만나면 다음 번으로 i+1이 전달됩니다.

• 3. 왼쪽 괄호의 연산을 종료하고 제품 개수를 0으로 설정합니다. i = 마지막 항목이 있는 위치 오른쪽 대괄호가 닿았습니다. 오른쪽 대괄호 밖의 나머지 문자를 계속 추가합니다.

특정 아이디어: 문자열을 왼쪽에서 오른쪽으로 구문 분석합니다.

• 현재 위치가 숫자인 경우 대괄호로 표시되는 문자열을 포함해야 합니다. 이 경우 k[... ]:

• 먼저 숫자를 구문 분석한 다음 왼쪽 대괄호를 구문 분석하고 다음 내용을 재귀적으로 구문 분석하고 해당 오른쪽 대괄호를 만나면 반환할 수 있습니다. 이때 구문 분석된 숫자를 기반으로 숫자 x를 구문 분석할 수 있습니다. 괄호 안의 문자열 s'는 새로운 문자열을 구성합니다. 현재 위치는 문자 위치이므로 현재 문자를 직접 구문 분석한 다음 이 문자 뒤의 내용을 아래쪽으로 재귀적으로 구문 분석합니다.

• 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]-&#39;0&#39;)
  			} else if isLetter(s[i]) {
  				str += string(s[i])
  			} else if s[i] == &#39;[&#39; {
  				item, index := decode(i + 1)
  				for num != 0 {
  					str += item
  					num--
  				}
  				i = index
  			} else if s[i] == &#39;]&#39; {
  				end = i
  				break
  			}
  		}
  		return str, end
  	}
  	res, _ := decode(0)
  	return res
  }
  func isLetter(u uint8) bool {
  	return u >= &#39;A&#39; && u <= &#39;Z&#39; || u >= &#39;a&#39; && u <= &#39;z&#39;
  }
  func isNumber(u uint8) bool {
  	return u >= &#39;0&#39; && u <= &#39;9&#39;
  }

  시간 복잡도: O(N)

공간 복잡도: O(N)

위 내용은 문자열 디코딩에 Go Java 알고리즘을 사용하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!