文字列の順列チェックをするアルゴリズムの概要とJuliaサンプルコード

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

作者:大槻兼資
発売日: 2020/10/02
メディア: 単行本（ソフトカバー）

目的

文字列の順列チェックをするアルゴリズムについて理解する。
アルゴリズムを実行するコードを実装してみて動作を確認する。

順列チェック問題とは

2つの文字が与えられたとき、片方がもう片方の並び替えになっているかを判定する問題。
コーディング面接などで出題された際は、大文字と小文字を区別する必要があるかを確認する。
空白が意味を持つかも考える必要がある。
2つの文字列の長さが異なる場合は、互いに順列になることはない。

アルゴリズムの概要とサンプルコード

GitHub

後述する2種類のアルゴリズムをそれぞれJuliaで実装した。
実装したコードは下記のGitHubリポジトリで公開している。

github.com

与えられた文字列をソートする方法

全体サンプルコード

module SortPermuChecker
    # methods
    function check_permu_sort(str1, str2)
        println("")
        println("Check $(str1) and $(str2) are Permutaton or not")
        len_1 = length(str1)
        len_2 = length(str2)

        # string length is not same
        # can not be permutation
        if len_1 != len_2
            println("Not Permutation")
            return false
        end

        # sort both strings
        str1_sub = join(sort!(split(str1, "")))
        str2_sub = join(sort!(split(str2, "")))

        # compare sorted strings
        for i in 1:len_1
            if str1_sub[i] != str2_sub[i]
                println("Not Permutation")
                return false
            end
        end

        println("Permutation")
        return true
    end

    function main()
        @time println(check_permu_sort("test", "sett"))
        @time println(check_permu_sort("test", "ttew"))
        @time println(check_permu_sort("test", "testtest"))
    end
end

if abspath(PROGRAM_FILE) == @__FILE__
    using .SortPermuChecker
    SortPermuChecker.main()
end

順列であれば、お互いの文字列は同じ文字が使われている。
そのため、アルファベット順にソートすれば両者は同じ文字列になる。
文字列のままソートはできないので、まずは1文字ずつの文字配列に分割してからソートし、最後にそれを結合して文字列に戻す。

# string length is not same
# can not be permutation
if len_1 != len_2
    println("Not Permutation")
    return false
end

# sort both strings
str1_sub = join(sort!(split(str1, "")))
str2_sub = join(sort!(split(str2, "")))

# compare sorted strings
for i in 1:len_1
    if str1_sub[i] != str2_sub[i]
        println("Not Permutation")
        return false
    end
end

同じ文字の数を数える方法

全体サンプルコード

module CountPermuChecker
    # parameters
    const max_size = 256

    # methods
    function check_permu_count(str1, str2)
        println("")
        println("Check $(str1) and $(str2) are Permutaton or not")

        # initialize count array
        count1 = [0 for i in 1:max_size]
        count2 = [0 for i in 1:max_size]

        # increment count of each character
        for s in str1
            count1[Int(s)] += 1
        end
        for s in str2
            count2[Int(s)] += 1
        end

        # string length is not same
        # can not be permutation
        if length(str1) != length(str2)
            println("Not Permutation")
            return false
        end

        # compare count array
        for i in 1:max_size
            if count1[i] != count2[i]
                println("Not Permutation")
                return false
            end
        end

        println("Permutation")
        return true
    end

    function main()
        @time println(check_permu_count("test", "sett"))
        @time println(check_permu_count("geeksforgeeks", "forgeeksgeeks"))
        @time println(check_permu_count("abcdefg", "aabbccd"))
        @time println(check_permu_count("hogehoge", "hogeehoge"))
    end
end

if abspath(PROGRAM_FILE) == @__FILE__
    using .CountPermuChecker
    CountPermuChecker.main()
end

2つの文字列が順列であれば、それぞれの中で登場する文字の頻度は一致する。
ハッシュテーブルのように動作する配列を定義し、各文字の登場頻度をマッピングする。
最後に、各文字の登場頻度を比較し、全て一致すれば順列と判定する。

# initialize count array
count1 = [0 for i in 1:max_size]
count2 = [0 for i in 1:max_size]

# increment count of each character
for s in str1
    count1[Int(s)] += 1
end
for s in str2
    count2[Int(s)] += 1
end

# string length is not same
# can not be permutation
if length(str1) != length(str2)
    println("Not Permutation")
    return false
end

# compare count array
for i in 1:max_size
    if count1[i] != count2[i]
        println("Not Permutation")
        return false
    end
end