LeetCoding Challenge Oct. 12: Buddy Strings

LeetCode October Challenge の 12 日目。

今日の問題は Buddy Strings。

問題の概要

• 与えられた ２ つの文字列 A, B が、一方の文字列のとある 2 つの位置 i, j (i != j) の文字を入れ替えた文字に等しい (true) か否か (false) を判定する

考え方

• これは愚直にやれば解ける問題ではなかろうか 🤔
  • 文字列の長さが異なれば false ("" / "aa" のケース)
  • それぞれの文字列の、同じ位置の文字を順に比較していって、
    • 差異が 2 つなら true ("ab" / "ba" のケース)
    • 差異が 1 つだけ、もしくは 3 つ以上なら false
    • 差異が 0 の (すなわち文字列が等しい) 場合は、いずれかの文字が 2 回以上使われていれば true ("aa" のケース)
• とりあえず実装していこう
  • 文字の差異があった回数を数えるカウンタを用意しよう
    • これが 3 以上になったら、問答無用で false を返す
    • カウンタが 1 のときは、そのときの A, B それぞれの文字を変数にとっておく
      • char の変数 2 つ じゃなくて、int の変数 1 つに詰めて保持するよ！
    • カウンタが 2 になったら、カウンタが 1 になったときに取っておいた文字と比較する
      • 比較演算は 1 回で済ませられる 😇
  • 文字が A, B で同じだった場合は、出現した文字を記録しておく
    • Set<Character> な変数を用意してそこに Set#add() する方法もあるけど、lowercase letter しか出現しないことが明らかなので int の変数にビットで記録する方法を採用するよ
    • ある文字が文字列中で 2 回以上使われているかどうかを確認するには、Integer.bitCount(ビットで記録している変数) < A.length() とすれば OK 👍
• 実装して submit → (何度かの wrong answer を経て 💦) → acdept 🤗
  • Runtime 1ms, Your runtime beats 99.31 % of java submissions. でした

コード

class Solution {
    public boolean buddyStrings(String A, String B) {
        int lengthA = A.length();
        if (lengthA != B.length()) {
            return false;
        }

        int diffChars = 0;
        int usedChars = 0;
        int diffCount = 0;

        for (int i = 0; i < lengthA; i++) {
            char chA = A.charAt(i);
            char chB = B.charAt(i);
            if (chA != chB) {
                diffCount++;
                if (diffCount == 1) {
                    diffChars = chA << 16 | chB;
                } else if (diffCount == 2) {
                    if ((chB << 16 | chA) != diffChars) {
                        return false;
                    }
                } else {  // diffCount >= 3
                    return false;
                }
            } else {
                usedChars |= 1 << (chA - 'a');
            }
        }

        if (diffCount == 2) {
            return true;
        }
        if (diffCount == 0 && Integer.bitCount(usedChars) < lengthA) {
            return true;
        }

        return false;
    }
}