読者です 読者をやめる 読者になる 読者になる

Powershellでアナグラムの判定をする

Powershell

技術面接で出された問題 - esm アジャイル事業部 開発者ブログ

上記のエントリを読んでPowershellだとどうやって実装するかなーと思ったので、テキトーに試す。

ソートだとこんな感じ?*1

[String]$a="ABCB"
[String]$b="BCAB"

if($a -eq $b){return $false} # 完全に一致する場合はアナグラムではないのでNG

#$aと$bをソートした上で比較する。一致すればアナグラム。
$aa=""
$bb=""
if(($a.ToCharArray() | Sort-Object | %{$aa=$aa + $_}) -eq ($b.ToCharArray() | Sort-Object | %{$bb=$bb + $_})){return $true}else{return $false}

AとBに含まれる文字ごとの個数が一致すればOKのはずなので、もうちょっと真面目に書くとこんな感じ?

[String]$a="ABCB"
[String]$b="BCAB"

if($a -eq $b){return $false} #完全に一致する場合はアナグラムではないのでNG

$hash1=@{}

$a.ToCharArray() | %{if($hash1.ContainsKey($_)){$hash1[$_]=$hash1[$_]+1}else{$hash1[$_]=1}};
$b.ToCharArray() | %{if($hash1.ContainsKey($_)){$hash1[$_]=$hash1[$_]-1}else{$hash1[$_]=-1}};

$flg=$true

$hash1.Values | %{if($_ -ne 0){$flg=$false}} 

return $flg

関数として使えるものにするなら、以下のようなこともしなくてはならないけど、まあこんな感じで実装できそうだということの確認にはなった。

  • 引数で文字列を受けとれるようにする
  • 引数チェックする($nullチェックとか?)
  • 性能評価*2

*1:ソートはもう少しましなやり方があるような気もするのだけれど、”配列の比較”の実装に悩んでしまったので、ソートした後に文字列として連結して比較している。単純に-eqなどで比較すると同一オブジェクトかどうかを比較してしまうので

*2:ちょっと真面目に書いた方はおそらくO(n)にはなっていると思うけど。