Suppression répétée d'une sous-chaîne d'une chaîne

Question

Problème: Supprimez plusieurs fois la sous-chaîne t d'une chaîne s et imprimez le nombre d'étapes nécessaires pour faire de même.

Exemple:t = ab, s = aabb. Dans la première étape, nous vérifions si t est contenue dans s. Ici, t est contenu au milieu, c'est-à-dire a(ab)b. Donc, nous allons l'enlever et le résultat sera ab et incrémenter la valeur de comptage par 1. Nous vérifions à nouveau si t est contenu dans s. Maintenant, t est égal à s, c'est-à-dire (ab). Donc, nous supprimons cela de s et incrémenter le nombre. Donc, puisque t n'est plus contenu dans s, on arrête et on imprime la valeur de comptage, qui est 2 dans ce cas.

J'ai essayé de résoudre ce en utilisant récursion

static int maxMoves(String s, String t) { 
    if (null == s || "" == s || null == t || "" == t){ 
      return 0; 
    } 
    int i = s.indexOf(t); 
     if(i != -1) { 
      return maxMoves(s.substring(0, i)+ s.substring(i+t.length(),       s.length()), t) + 1; 
     } else { 
      return 0; 
     } 

    } 

Mais je ne font qu'emprunter 9/14 cas de test. J'ai également essayé ceci,

static int maxMoves(String s, String t) { 
    int count = 0,i; 

    while(true) 
    { 
     if(s.contains(t)) 
     { 
      i = s.indexOf(t); 
      s = s.substring(0,i) + s.substring(i + t.length()); 
     } 
     else break; 

     ++count; 
    } 

    return count; 
} 

Mais cela a également passé seulement 9/14 cas.

Quelqu'un pourrait-il m'aider à déterminer quels cas je ne couvre pas?

Answer 1

simplement vous pouvez utiliser String::replaceFirst avec une boucle while par exemple:

String s = "aabb"; 
String t = "ab"; 
int count = 0; 
while (s.contains(t)) { 
    s = s.replaceFirst(Pattern.quote(t), ""); 
    count++; 
} 

System.out.println(count); 

Answer 2

Un moyen facile et efficace est d'accumuler la chaîne de caractère par caractère dans un StringBuilder; si à tout moment sa mémoire tampon se termine par la chaîne que vous voulez remplacer, supprimer:

StringBuilder sb = new StringBuilder(); 
int c = 0; 
for (int i = 0; i < s.length(); ++i) { 
    sb.append(s.charAt(i)); 
    int last = sb.length()-t.length(); 
    if (last >= 0 && sb.indexOf(t, last) == last) { 
    sb.setLength(last); 
    ++c; 
    } 
} 
// c is now the number of times you removed t from s. 

Answer 3

Utilisez String#replace

String s = "aabb"; 
String oldstr = s; 
String x = "ab"; 
while(s.contains(x)){ 
    s = s.replace(x, ""); 
} 
System.out.println((oldstr.length()-s.length())/x.length());