以下の問題を解くための手法として「2つの文字列を順方向・逆方向それぞれに走査し、一致する部分の最大長を求める」というものが公式解説に用意されており、ほとんど典型手法と見なされている(諸説あり)にもかかわらず、ライブラリを用意していなかったので作成しました
AtCoder Beginner Contest 324 C - Error Correction
※該当問題ではcountDifferenceIfSameLengthメソッドを利用することはありませんでしたが個人的な判断で残しているだけなので不要ならば削除でOKです。個人的にはこのクラスに対して最良の命名をできてはいない感覚でいますが、これ以上に良いクラス名を思いつくことができませんでした
public final class StringScanner {
/**
* 2つの文字列を順方向に走査し、一致する文字数を返す
* @param s1 1つ目の文字列
* @param s2 2つ目の文字列
* @return 2つの文字列を順方向に走査した時、一致しない文字が初登場するまでの長さ(先頭が不一致の場合は0)
*/
public static final int countSameCharactersForward(String s1, String s2) {
if (s1.length() > s2.length()) {
return countSameCharactersForward(s2, s1);
}
int res = 0;
for (int i = 0, f = s1.length(); i < f; ++i) {
if (s1.charAt(i) == s2.charAt(i)) {
++res;
} else {
break;
}
}
return res;
}
/**
* 2つの文字列を逆方向に走査し、一致する文字数を返す
* @param s1 1つ目の文字列
* @param s2 2つ目の文字列
* @return 2つの文字列を逆方向に走査した時、一致しない文字が初登場するまでの長さ(末尾が不一致の場合は0)
*/
public static final int countSameCharactersBackward(String s1, String s2) {
if (s1.length() > s2.length()) {
return countSameCharactersBackward(s2, s1);
}
final int offset = s2.length() - s1.length();
int res = 0;
for (int i = s1.length() - 1; i >= 0; --i) {
if (s1.charAt(i) == s2.charAt(offset + i)) {
++res;
} else {
break;
}
}
return res;
}
/**
* 2つの文字列を走査し、各インデックスに対応する文字列中の文字のうち一致しないものの数を返す
* @param s1 1つ目の文字列
* @param s2 2つ目の文字列
* @return 2つの文字列の長さが等しい場合、一致しない文字数を返し、等しくない場合は-1を返す
*/
public static final int countDifferenceIfSameLength(String s1, String s2) {
if (s1.length() != s2.length()) {
return -1;
}
int res = 0;
for (int i = 0, f = s1.length(); i < f; ++i) {
if (s1.charAt(i) != s2.charAt(i)) {
++res;
}
}
return res;
}
}
<余談>
countSameCharactersBackwardメソッドに関して、最初は以下のような実装でしたが、String.formatを使用して文字列長を揃えるように正規化させる処理の実行回数が多くなると急激に実行速度が落ちてTLEの原因となるようなので上記のように修正しました
static final int countSameCharactersBackward(String s1, String s2) {
if (s1.length() > s2.length()) {
return countSameCharactersBackward(s2, s1);
} else if (s1.length() < s2.length()) {
return countSameCharactersBackward(String.format("%" + s2.length() + "s", s1), s2);
}
int res = 0;
for (int i = s1.length() - 1; i >= 0; --i) {
if (s1.charAt(i) == s2.charAt(i)) {
++res;
} else {
break;
}
}
return res;
}