アナグラム判定処理をPHPで書いてみる

PHP,勉強,転職活動

やってみようと思ったきっかけ

以前面接でクイックソートについてのコーディングテストがあったが、今日また別の会社の面接でアナグラム判定の問題が出た。忘れないうちに振り返りをしておく。

そもそも「アナグラム」というものについてあまり知らなかったため、そちらの概要はご教示頂いた。要するに文字を入れ替えた文章であるかどうかを判定するということらしい。例えば’ameba’と’abema’はアナグラムであるということ。

コーディングテストがあるとは聞いていたが、まさか今回の面接で行われるとは考えていなかったため宣言を受けた際は非常に緊張した。30分ほどで解いてください、と2問だされたのだが、アナグラム問題に手こずり過ぎて2問目までたどり着けず少し落ち込んだ。コーディングテストを受けるのは非常に緊張する。今回の面接結果はまだ出ていないが、2問目に手をつけられなかったテストの出来を鑑みるに、通らない気がする。

とりあえず完成コード

<?php
/**
 * 主処理
 * @param string $left
 * @param string $right
 *
 * @return bool
 */
function isAnagram(string $left, string $right): bool
{
    // 同じ文字列はアナグラムではないとする
    if ($left === $right) {
        return false;
    }

    // 1文字ずつ文字列のカウントを取得する
    $leftCounts = createCharCounts($left);
    $rightCounts = createCharCounts($right);

    // 要素数の差分があった場合早期リターン
    if (count($leftCounts) !== count($rightCounts)) {
        return false;
    }

    // 左右比較
    if (count(array_diff_assoc($leftCounts, $rightCounts)) > 0) {
        return false;
    }
    if (count(array_diff_assoc($rightCounts, $leftCounts)) > 0) {
        return false;
    }
    return true;
}

/**
 * 文字の出現回数配列を作成
 * @param string $target
 *
 * @return array
 */
function createCharCounts(string $target): array
{
    $charCounts = [];
    for ($i = 0; $i < mb_strlen($target); $i++) {
        $targetChar = mb_substr($target, $i, 1);
        if (isset($charCounts[$target])) {
            continue;
        }
        $charCounts[$targetChar] = mb_substr_count($target, $targetChar);
    }
    return $charCounts;
}


$a = 'isanagram';
$b = 'anagramis';

$c = 'thisisanagram';
$d = 'isthisanagram?';

var_dump(isAnagram($a, $b)); // true
var_dump(isAnagram($c, $d)); // false

解説

与えられた前提条件は「同じ文字列はアナグラムではないとする」という条件。

回答のコンセプトは「同じ並びの文字列でなく、かつ各1文字の出現回数が一緒であればアナグラムである」と考えた。判定をしているのを主処理isAnagram()、各文字の出現回数を保存する連想配列を作っているのをcreateCharCounts()とした。大文字小文字の判別やmulti byte文字の指定はなかったのでその辺りは一旦無視して(できるだけmb_系関数を使う意識をもつ程度に)考えた。提出コードのstrlenはmbに対応させていなかったような気がする。

元々はarray_diff()で書いていたが、試験終了後に「array_diffって連想配列うまく処理できたっけ?」と不安になったのでこの記事執筆中にarray_diff_assocへと書き換えた。array_diff自体は何度か使用したことがあるが、array_diff_assocは使ったことがなかった。こちらの関数ではkeyも値も比較してくれるらしいので、今回のケースではこちらの方がより厳密でありふさわしいように思う。array_udiff()でより厳密に比較処理を書いても良い。

振り返り

今回は時間配分の戦略立てがうまくいかなかった。前回のクイックソートと同様、志望度が高い企業だったため、そもそも面接自体に非常に緊張してしまった。2問目までいけなかった上に、このアナグラム判定さえ満足できるコードにはならなかった。自分のダメなところに引っ張られた気がする。今回の解法コンセプト自体は割と早期に思いつけたのだが、それを実装しようとすると「ここも気をつけなきゃな」と気になる点が増えてしまい、思考の枝葉が増えてしまった。どうにか時間内に完璧なコードを提出してみたい。時間内に提出できたのは上記コードの95%程度。つまり2問あるテスト全体から見れば40%台となる。これは落ちても仕方がない。

振り返ると、この程度のコードを30分で書ききれなかった大きな原因はstrlenやsubstrの引数ってどういう順番だっけと一々公式ドキュメントを読みに行ってしまったこと。これはPHPのせいというよりは緊張のせい。経験年数的には基礎的な関数は暗記できていて当たり前だと判断されるので、その辺りも意識して普段からコードを書くようにしたい。

反省してばかりだと苦しくなってしまうので、とりあえず今回の面談で今月の目標「何社か面談を受ける」は達成として自分を慰めたい。

今月もあと10日ほど。リポジトリ公開関連の目標がまだ全然進捗していないことだし、がんばっていこう。

PHP,勉強,転職活動

Posted by shoopon