文字列から部分文字列を繰り返し削除する

Question

問題：文字列sから部分文字列tを繰り返し削除し、同じ手順を実行します。

例：t = ab,s = aabb。最初のステップではtがsに含まれているかどうかを確認します。ここで、tは中間に含まれ、すなわちa(ab)bである。そこで、それを除去すると、結果はabになり、カウント値は1だけインクリメントされます。 tがsに含まれているかどうか再度確認します。今、tは、s、すなわち(ab)に等しい。そこで、それをsから削除し、カウントを増やします。したがって、tはsに含まれていないため、カウント値を停止して印刷します（この場合は2）。

私は、この使用して再帰

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; 
     } 

    } 

を解決しようとしましたが、私は9/14のテストケースを渡しています。私もこれを試しました

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; 
} 

しかし、それはまた9/14のケースを渡しただけです。

私はどのケースをカバーしていないのか分かりませんか？

Answer 1

単にあなたは、例えばwhileループでString::replaceFirstを使用することができます。

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

簡単かつ効率的な方法は、StringBuilderの文字列文字ずつ蓄積することです。任意の時点でそのバッファが置き換えたい文字列で終了した場合、それを削除します。

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

使用使用しない理由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());