文字列の距離

Haskell 30分プログラム

30分プログラム、その113。文字列の距離をやってみる。

本当はモナドやら動的計画法のイントロの問題らしいんだけど、疲れているのでさわりの部分だけ。

2つの文字列の間の距離を計算するプログラムを書け。

文字列間の距離とは、一方の文字列をもう一方の文字列に変換する時に必要な操作の回数である。文字列に対する操作には次の3つがある。

  • 1文字を取り除く
  • 1文字を加える
  • 1文字を任意の1文字で置き換える

例えば、pascal と haskell の距離は、p を h に変え、c を k に変え、a を e に変え、最後に l を追加すればいいので4である。

使い方

$ distance hoge hage
1

$ distance pascal haskell
4

ソースコード

import System.Environment

distance :: String -> String -> Int
distance xs [] = length xs
distance [] ys = length ys
distance left@(x:xs) right@(y:ys) = 
    minimum [(if x == y then 0 else 1) + (distance xs ys),
             1+(distance xs right),
             1+(distance left ys)]

main = do (x:y:_) <- getArgs
          putStrLn $ show $ distance x y

参考