共通した最も長い接頭語を求める(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にありました。