IT練習ノート

IT関連で調べたこと(実際は嵌ったこと)を書いています。

共通した最も長い接頭語を求める(Longest Common Prefix)

["abcdefg", "abcxyz", "abcaaaaa"] からabcを求める。

たとえば、Javaであれば、このリンク先にあるようなロジックになる。

LeetCode – Longest Common Prefix (Java)

一見すると、ループが多い印象。

これをHaskellで実装するとどうなるかを考えてみた。

試行錯誤してみる。

まずは、配列の要素が2つの問題を考えてみる。

要素が2個なら、条件を与えつつzipperができるzipWithを使ってみる。

Prelude> zipWith (\x y -> if (x==y) then x else ' ') "abcd" "abce"
"abc "
Prelude> 

ただ、これでは要素が3つ以上になったときに使えない。。

そこで、配列を転置してみる。

["abcdef", "abcxyz", "abcaaa"]

["aaa","bbb","ccc","dxa","eya","fza"]

にしてみる。

そうすると、同じ文字で構成される文字列を拾えば良さそう。

転置は、検索すると、下記で出来ることが分かる。

algorithm - Understanding this matrix transposition function in Haskell - Stack Overflow

同じ文字で構成される文字列の場合にその1文字を求めるには、こんな感じで出来そう。

compact :: String -> String
compact (x:[]) = [x]
compact (x:xs) = if x == head xs
                   then compact xs
                   else []
*Main> compact "aaabbb"
""
*Main> compact "aaaaaaa"
"a"
*Main> compact "aabaaaa"
""

このcompact関数を、元の文字列の配列を転置した配列に適用する。

*Main> map compact $ transpose ["abcdef", "abcxyz", "abcaaa"]
["a","b","c","","",""]
*Main> 

このままだと、求める文字列にはなっていない。文字の配列の配列になっているので、一階層配列をはがしてやる必要がある。

なので、comcatしてやる。

*Main> concat $ map compact $ transpose ["abcdef", "abcxyz", "abcaaa"]
"abc"
*Main> 

まとめると、

compact :: String -> String
compact (x:[]) = [x]
compact (x:xs) = if x == head xs
                   then compact xs
                   else []

transpose:: [[a]]->[[a]]
transpose ([]:_) = []
transpose x = (map head x) : transpose (map tail x)

lcp :: [String] -> String
lcp x = concat $ map compact $ transpose x

zipWithで難しいかと思いましたが、畳み込みを使えば出来ますね。ただ、最後にトリムするのが野暮ったいですが。

*Main> foldr1 (zipWith (\x y -> if (x==y) then x else ' ')) ["abcdef", "abcxyz", "abcaaa"]
"abc   "
*Main> foldr (\a b -> if a==' ' then b else a:b) [] "   abc   "
"abc"
*Main> foldr (\a b -> if a==' ' then b else a:b) [] $ foldr1 (zipWith (\x y -> if (x==y) then x else ' ')) ["abcdef", "abcxyz", "abcaaa"]
"abc"
*Main> 

尤も、もっと分かりやすい方法がStackOverflowにありました。

list - Longest common prefix in Haskell - Stack Overflow