Comment utiliser l'algorithme Go Java pour le décodage de chaînes ?
- WBOYavant
- 2023-04-25 23:52:061190parcourir
String Decoding
Étant donné une chaîne codée, renvoie sa chaîne décodée.
La règle d'encodage est : k[encoded_string], ce qui signifie que la encoded_string entre crochets est répétée k fois. Notez que k est garanti être un entier positif.
Vous pouvez supposer que la chaîne d'entrée est toujours valide ; il n'y a pas d'espaces supplémentaires dans la chaîne d'entrée et les crochets d'entrée répondent toujours aux exigences de format.
De plus, vous pouvez penser que les données originales ne contiennent pas de chiffres. Tous les nombres ne représentent que le nombre de répétitions k. Par exemple, il n'y aura pas de saisie comme 3a ou 2[4].
Exemple 1 :
Entrée : s = "3[a]2[bc]"
Sortie : "aaabcbc"
Exemple 2 :
Entrée : s = "3[a2[c]]"
Sortie : "accaccacc"
Exemple 3 :
Entrée : s = "2[abc]3[cd]ef"
Sortie : "abcabccdcdcdef" "
Exemple 4 :
Entrée : s = "abc3[cd]xyz"
Sortie : "abccdcdcdxyz"
Méthode 1 : Stack (Java)
Voir la correspondance des parenthèses, La première chose qui vient à l’esprit est d’utiliser la pile pour résoudre le problème.
Tout d'abord, comme le numéro peut avoir plus d'un chiffre, pour plus de clarté et de commodité, vous pouvez utiliser deux piles, une pour stocker les numéros et l'autre pour stocker les caractères. Lorsqu'un caractère autre que ] est rencontré, il est d'abord placé dans la pile de caractères. Lorsqu'un nombre est rencontré, le nombre complet est converti et placé dans la pile de nombres. Lorsque ] est rencontré, les caractères jusqu'à [ sont supprimés. la pile de caractères pour former une chaîne temporaire et est sorti. L'élément supérieur de la pile de nombres, répétez la chaîne temporaire le nombre de fois, puis remettez-la dans la pile de caractères.
Après avoir parcouru la chaîne d'origine de gauche à droite, l'élément de la pile est la réponse finale
Idée de méthode spécifique : parcourir cette pile
Si le caractère actuel est un chiffre, analyser un nombre (plusieurs chiffres consécutifs ) Et poussez-le sur la pile
Si le caractère actuel est une lettre ou un crochet gauche, poussez-le directement sur la pile
Si le caractère actuel est un crochet droit, commencez à le faire sortir de la pile jusqu'à ce que le Le crochet gauche est sauté. La séquence de saut est inversée et fusionnée. Pour une chaîne, le nombre en haut de la pile retiré à ce moment est le nombre de fois que cette chaîne doit apparaître. Nous construisons une nouvelle chaîne sur cette base. nombre et la chaîne et poussez-la sur la pile
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();
}
}Complexité temporelle : O(N)
Complexité spatiale : O(N)
Méthode 2 : Récursion (Go)
La méthode mentionnée ci-dessus utilise la pile, on peut donc alors penser à utiliser la récursivité pour le compléter. Pour des idées récursives spécifiques, veuillez voir ci-dessous.
Besoin de résoudre le problème d'imbrication entre plusieurs supports. Autrement dit, des sous-problèmes qui se chevauchent. Vous pouvez utiliser la pile ou la récursivité pour résoudre des problèmes.
1. Identifiez d’abord la position où se termine le support droit.
2. Lorsque vous rencontrez un support gauche, i+1 est passé à la prochaine fois
3. Terminez l'opération du support gauche et mettez le nombre de produits à zéro, i = la position où le dernier. support droit touché. Continuez à ajouter les caractères restants en dehors du crochet droit.
Idée spécifique : Analyser la chaîne de gauche à droite :
Si la position actuelle est un chiffre, alors elle doit contenir une chaîne représentée par des crochets, ce qui est le cas : k[... ] :
Nous pouvons d'abord analyser un nombre, puis analyser le support gauche, analyser récursivement le contenu suivant et revenir lorsque nous rencontrons le support droit correspondant. À ce stade, nous pouvons analyser le nombre x en fonction du nombre analysé. La chaîne s' entre parenthèses construit une nouvelle chaîne. La position actuelle est une position de lettre, nous analysons donc directement la lettre actuelle, puis analysons de manière récursive le contenu après cette lettre vers le bas.
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' }Complexité temporelle : O(N)
Complexité spatiale : O(N)
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!