문자열 디코딩에 Go Java 알고리즘을 사용하는 방법은 무엇입니까?
- WBOY앞으로
- 2023-04-25 23:52:061239검색
문자열 디코딩
인코딩된 문자열이 주어지면 디코딩된 문자열을 반환합니다.
인코딩 규칙은 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 == '[') {
// 获取一个字母并进栈
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]-'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 알고리즘을 사용하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!