1題のアルゴリズム|繰り返し重ね合わせ文字列マッチング
4653 ワード
タイトル
2つの文字列AとBが与えられ、重複する重複する文字列Aの最小回数が、文字列Bが重複する文字列Aのサブ列となり、存在しない場合は−1を返す
例
例えば、A=「abcd」、B=「cdabcdab」である.答えは3で、Aが3回繰り返して「abcdabcdabcd」になったため、Bはそのサブ列である.Aは2回繰り返して「abcdabcd」となり、Bはそのサブ列ではない.
に注意
AとB文字列の長さは1と10000区間の範囲内である
問題を解く構想.
まず、終了条件、すなわち
インプリメンテーションコード
コードをスキャンして公衆番号(公衆番号を検索します:平頭兄の技術の博文)に注目して一緒に交流して勉強します
2つの文字列AとBが与えられ、重複する重複する文字列Aの最小回数が、文字列Bが重複する文字列Aのサブ列となり、存在しない場合は−1を返す
例
例えば、A=「abcd」、B=「cdabcdab」である.答えは3で、Aが3回繰り返して「abcdabcdabcd」になったため、Bはそのサブ列である.Aは2回繰り返して「abcdabcd」となり、Bはそのサブ列ではない.
に注意
AとB文字列の長さは1と10000区間の範囲内である
問題を解く構想.
まず、終了条件、すなわち
A
コピーの最大文字列長を見つけます.A
の長さがB
の長さより大きい場合、A
はB
文字列を含まない文字列を2回コピーすると、後で含めることはできません.この場合の最大長は2*A.length
です.A
の長さがB
の長さより小さい場合、コピーA
の文字列長がA.length+B.length
である場合、A
の文字列にB
の文字列が含まれていなければ、後にも含まれず、このときの最大長はA.length+B.length
である.両者を組み合わせて最大値A.length*2+B.length
をとる.インプリメンテーションコード
public static int repeatedStringMatch(String A, String B) {
//
int max_length = (A.length()*2 + B.length()) < 10000 ? (A.length()*2 + B.length()) : 10000;
// A
StringBuilder sb = new StringBuilder(A);
//
int repeated_count = 1;
while (sb.length()<= max_length){
if (sb.lastIndexOf(B) > -1){
return repeated_count;
}
repeated_count++;
sb.append(A);
}
return -1;
}
コードをスキャンして公衆番号(公衆番号を検索します:平頭兄の技術の博文)に注目して一緒に交流して勉強します