並べ替えて同じ言葉になるか｜コーディング面接問題

問題

英小文字だけでできた 2 つの文字列 a と b を受け取ります。a の文字の順を並べ替えて b と同じにできるなら true、できないなら false を返す関数を書いてください。

文字を足したり消したりはできません。並べ替えるだけです
同じ文字が何回出るかも、ぴったりそろっている必要があります
a と b の長さは、どちらも 0 以上 10000 以下です

入力と出力の例

例 1

入力

a = "below"
b = "elbow"

出力

true

例 2

使っている文字の種類は同じでも、数が違えば並べ替えて同じにはできません。

入力

a = "aab"
b = "abb"

出力

false

例 3

長さが違えば、それだけで答えは決まります。

入力

a = "note"
b = "notes"

出力

false

面接での聞かれ方

面接では、例を添えて短く渡されることが多いです。

「2 つの単語が、文字の並べ替えで同じになるかを判定してください」
書き終えたあとに「いまの書き方の計算量は？」「並べ替えずにできますか？」と続けて聞かれます
「大文字や空白が入ったら？」「日本語なら？」と、入力が広がったときの話を聞かれることもあります

使う文字が英小文字だけなのか、大文字と小文字を同じに見るのかを、最初に確かめておきます。文字の種類が決まると、数え方も選びやすくなります。

まず考える手順

段 1

まずは素直に、両方の文字を並べ替えてから比べます。並べ替えて同じにできる 2 つなら、どちらも文字を順に並べると同じ文字列になります。Python なら sorted(a) == sorted(b) で書けます。

段 2

並べ替えは、長さを n とすると O(n log n) の時間がかかります。けれど、ほしいのは順ではなく「どの文字が何回出たか」だけです。並べ替えずに、文字ごとの回数を数えて比べれば足ります。

段 3

辞書 (Python の dict、JavaScript の Map) に、a の文字の回数を数えて入れます。次に b を読みながら、その文字の回数を 1 つずつ減らします。減らす前に 0 になっていたら、b の方が多いので false です。先に長さを比べておけば、最後まで読み切れたときは回数がちょうど打ち消し合っています。

ここから解答です。先に自分で書いてから読むと、考え方が残ります。

解答

Python

def same_letters(a, b):
    if len(a) != len(b):
        return False
    count = {}
    for ch in a:
        seen = count.get(ch, 0)
        count[ch] = seen + 1
    for ch in b:
        have = count.get(ch, 0)
        if have == 0:
            return False
        count[ch] = have - 1
    return True

JavaScript

function sameLetters(a, b) {
  if (a.length !== b.length) {
    return false;
  }
  const count = new Map();
  for (const ch of a) {
    const c = count.get(ch);
    count.set(ch, (c ?? 0) + 1);
  }
  for (const ch of b) {
    const c = count.get(ch);
    if (!c) {
      return false;
    }
    count.set(ch, c - 1);
  }
  return true;
}

段 1 の並べ替える書き方なら、Python は sorted(a) == sorted(b) の 1 行です。短く書けるので、面接ではまずこちらを言い、そのあとで数える書き方に進むと流れが伝わります。

計算量

時間は O(n) です。a と b を 1 回ずつ読み、辞書を調べるのも書き換えるのも、平均して一定の手間で済みます
使う記憶は、文字の種類の数だけです。英小文字なら多くても 26 種類なので、O(1) と見なせます
段 1 の並べ替える書き方は、時間が O(n log n) で、並べ替えた写しのために記憶を O(n) 使います

よくある間違い

文字の種類だけを比べる。集合 (set) にして比べると、例 2 の aab と abb がどちらも a と b になり、true と答えてしまいます。回数まで比べます
長さを先に比べない。長さを比べずに b だけ読んで減らすと、a に余った文字があっても true を返します。例 3 なら、長さの違いを先に見れば迷いません
JavaScript で文字列をそのまま並べ替えようとする。 文字列には sort が無いので、[...a].sort().join("") のように、いったん並びにしてから並べ替えます

面接での話し方の例

書き始める前に、方針を短く口に出します。

「両方を並べ替えて比べれば O(n log n) で解けます。ただ、知りたいのは文字ごとの回数だけなので、辞書で数えれば O(n) になります。先に長さを比べて、a で数を足し、b で数を引きます。途中で足りなくなれば false です。」

書き終えたら、例を 1 つ手でたどって見せます。

「例 2 の aab と abb でたどります。長さはどちらも 3 です。a から数えると a が 2 回、b が 1 回です。b を読むと、a で 1 回減らし、b で 1 回減らし、次の b で残りが 0 なので、そこで false を返します。」

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026年10月24日