Pythonで2つの文字列の順列が辞書式順序の大小関係を満たすかどうかをチェックする方法

問題の概要

同じ長さ n を持つ2つの文字列 s と t が与えられたとき、次の条件を満たすような順列（並べ替え）が存在するかどうかを判定します。

• s のある順列 s1 と t のある順列 t1 について、すべての 0 ≤ i < n に対して s1[i] ≤ t1[i] が成り立つ、または
• すべての 0 ≤ i < n に対して t1[i] ≤ s1[i] が成り立つ

つまり、「どちらか一方の文字列を並べ替えることで、もう一方の文字列に対して各位置で常に小さい（または等しい）状態にできるか」という問題です。

入力例

たとえば、s = "vyx"、t = "wzx" という入力の場合、出力は True になります。実際、s1 = "vxy"、t1 = "wxz" と並べ替えれば、各位置で v ≤ w、x ≤ x、y ≤ z がすべて成り立つためです。

解法のアプローチ

この問題は、両方の文字列をあらかじめソートしておくことで効率的に解けます。手順は以下のとおりです。

1. s と t が空文字列の場合は True を返す
2. 文字列 s をソートする
3. 文字列 t をソートする
4. 補助関数 util() を定義する。引数として s1 と t1 を受け取る
5. i を 0 から s1 の長さまで繰り返し処理する：
   • s1[i] > t1[i] であれば False を返す
6. ループを最後まで抜ければ True を返す
7. メインの処理では以下を行う：
   • util(s, t) が真であれば True を返す
   • s と t を入れ替える
   • util(s, t) の結果を返す

なぜソートでうまくいくのか？

ある並べ替えによって「各位置で片方がもう片方以下」という関係が成立するなら、両方の文字列を昇順にソートした場合にも必ず同じ関係が成立します。ソートされた状態は最も整列した配置であり、大小比較が最も有利になるためです。したがって、順列の全パターンを試す必要はなく、ソート後の文字列同士を比較するだけで答えが分かります。計算量は O(n log n) に抑えられます。

Pythonでの実装例

class Solution:
    def solve(self, s, t):
        if not len(s) or not len(t):
            return True
        s = sorted(s)
        t = sorted(t)
        def util(s1, t1):
            for i in range(len(s1)):
                if s1[i] > t1[i]:
                    return False
            return True
        if util(s, t):
            return True
        s, t = t, s
        return util(s, t)

ob = Solution()
s = "vyx"
t = "wzx"
print(ob.solve(s, t))

入力

"vyx", "wzx"

出力

True

まとめ

この問題の鍵は「ソートすれば十分である」という性質に気づくことです。Pythonの sorted() を使って両方の文字列を昇順に並べ替え、要素ごとの比較を一度行い、成立しなければ文字列を入れ替えて再度比較するだけで、O(n log n) の計算量で答えを求められます。全順列を総当たりする非現実的な手法と比べて、非常にシンプルかつ高速な解法といえます。