EurekaMoments

This is my studying logs about Autonomous driving, Machine learning technologies and etc.

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

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

問題解決力を鍛える!アルゴリズムとデータ構造 (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

実行例

  • 2つの文字列を与えた際に、それらが順列かどうかを正しく判定できている。
  • お互いの文字数が異なる場合はその時点で処理を終了し、順列ではないと判定させている。

f:id:sy4310:20201005185459p:plain