スクラブル ボードでの移動を表すString呼び出しがあるとします。s"AARDV RK"
Scrabble 辞書全体 (~180,000 語!) を含む呼び出しHashSet<String>があります。dict
dict正規表現を使用して検索するにはどうすればsよいですか?ただし、空白文字は大文字を表しますか?
1382 次
3 に答える
0
説明
ランダムな文字を探す代わりに、プレイヤーの現在のタイルのトレイに収まるすべての単語を探すことができます。
次の正規表現とロジックの PowerShell の例を考えてみましょう。ここでは、ロジックを使用して、プレーヤーが現在持っているタイルに基づいて正規表現を作成しています。結果の正規表現には、1 とプレーヤーのトレイ内の各文字の合計数の間で一致する 2 つの異なる部分があり、2 番目の部分はプレーヤーのトレイ内の各文字の 0 と +1 の間で一致します。したがって、プレーヤーAのトレイに 2 があり、正規表現は 0 と 3 の間で一致しようとしAますが、他のすべての文字の各文字の合計数に 1 が必要です。このプロセスは、文字ごとに繰り返されます。
だからあなたの例を考えてください。プレイヤーがaarvfrkトレイに持っている場合、正規表現はすべての文字が like のすべての単語を検索しますがaardvark、aardvarksこれも一致しますが、後で単語の長さに基づいて一致を除外することでそれを排除しますwhere {$_.Length -le $($PlayerTiles.Length + 1)}。そのため、1 つの単語に 2 つ以上の余分なタイルを含めることはできず、プレイヤー トレイに存在することはできません。
次に、プレーヤーがトレイに現在持っていない、見つかった単語の文字を探すための正規表現を作成します。
確かに、プレーヤーが単語のスペルを 2 文字間違えた場合など、この特定のロジックが失敗する可能性があるエッジ ケースがあります。これらの単語を知っていると、特定のボード レイアウトに探している文字が含まれている可能性があるまれなケースで役立つ場合があります。ボードのレイアウトを評価し、プレーヤーのトレイの一部であるかのように、すべての単一文字をボードに含めることで、これを解決できます。この評価は、基板レイアウトのために使用できなかった文字を識別するのに十分スマートである必要があります。また、ボード レイアウトから複数の文字列を識別できるようにスマートにすることもできます。これは使用しても問題ありません。しかし、それはすべて、元の質問の範囲を超えています。
ノート
選択した言語によって*?は、後読みの を のようなものに置き換える必要がある場合があります{0,100}。これは、[ Java のような] 言語が後読みを実装する方法によるもので、文字列の検索が未定のサイズになる可能性があります。
ソースコード
$Matches = @()
[array]$Dictionary = @()
$Dictionary += 'AARDVARK'
$Dictionary += 'AARDVRKS'
$Dictionary += 'AARDVARKS'
$Dictionary += 'ANTHILL'
$Dictionary += 'JUMPING'
$Dictionary += 'HILLSIDE'
$Dictionary += 'KITTENS'
$Dictionary += 'LOVER'
$Dictionary += 'LOVE'
$Dictionary += 'LOVES'
$Dictionary += 'LOVELY'
$Dictionary += 'OLIVE'
$Dictionary += 'VOTE'
$PlayerTiles = "aardvrk"
Function funBuildRegexForPlayerTiles ([string]$GivenTiles) {
# split the GivenTiles so each letter is seperate, and store these in a hashtable so the letter is the keyname and the number times it's seen is the value, This deduplicates each letter
[hashtable]$SearchForTiles = @{}
foreach ($Letter in $GivenTiles[0..$($GivenTiles.Length - 1)] ) {
$SearchForTiles[$Letter] += 1
} # next letter
# build regex for tiles to match just the tiles we have
[string]$SameNumberRegex = ""
foreach ($Letter in $SearchForTiles.Keys) {
$SameNumberRegex += "(?=^([^$Letter]*?$Letter){1,$($SearchForTiles[$Letter])}(?![^$Letter]*?$Letter))"
} # next letter
# add to the regex to include one extra letter of each type.
[array]$ExtraLetterRegex = @()
foreach ($MasterLetter in $SearchForTiles.Keys) {
[string]$TempRegex = ""
foreach ($Letter in $SearchForTiles.Keys) {
if ($MasterLetter -ieq $Letter) {
# this forces each letter to allow zero to one extra of itself in the dictionary string. This allows us to match words which would have all the other letters and none of this letter
$TempRegex += "(?=^([^$Letter]*?$Letter){0,$($SearchForTiles[$Letter] + 1)}(?![^$Letter]*?$Letter))"
} else {
# All the rest of these tiles on this regex section will need to have just the number of tiles the player has
$TempRegex += "(?=^([^$Letter]*?$Letter){1,$($SearchForTiles[$Letter])}(?![^$Letter]*?$Letter))"
} # end if
} # next letter
$ExtraLetterRegex += $TempRegex
Write-Host "To match an extra '$MasterLetter': " $TempRegex
} # next MasterLetter
# put it all together
[array]$AllRegexs = @()
$AllRegexs += $SameNumberRegex
$AllRegexs += $ExtraLetterRegex
# stitch all the regexs together to make a massive regex
[string]$Output = $AllRegexs -join "|"
return $Output
} # end function funBuildRegexForPlayerTiles
Function funBuildMissingLetterRegex ([string]$GivenTiles) {
# split the GivenTiles so each letter is seperate, and store these in a hashtable so the letter is the keyname and the number times it's seen is the value, This deduplicates each letter
[hashtable]$SearchForTiles = @{}
foreach ($Letter in $GivenTiles[0..$($GivenTiles.Length - 1)] ) {
$SearchForTiles[$Letter] += 1
} # next letter
[array]$MissingLetterRegex = @()
# include any letters which do not match the current tiles
$MissingLetterRegex += "(?i)([^$($SearchForTiles.Keys -join '')])"
# build the regex to find the missing tiles
foreach ($Letter in $SearchForTiles.Keys) {
$MissingLetterRegex += "(?i)(?<=($Letter[^$Letter]*?){$($SearchForTiles[$Letter])})($Letter)"
} # next letter
[string]$Output = $MissingLetterRegex -join "|"
return $Output
} # end function
[string]$Regex = funBuildRegexForPlayerTiles -GivenTiles $PlayerTiles
Write-Host "Player tiles '$PlayerTiles'"
Write-Host "Regex = '$Regex'"
Write-Host "Matching words = "
$MatchedWords = $Dictionary -imatch $Regex | where {$_.Length -le $($PlayerTiles.Length + 1)}
[string]$MissingLetterRegex = funBuildMissingLetterRegex $PlayerTiles
foreach ($Word in $MatchedWords) {
Write-Host $Word -NoNewline
# find all the letters for which the player doesn't have a matching tile
[array]$MissingTiles = ([regex]"$MissingLetterRegex").matches($Word) | foreach {
Write-Output $_.Groups[0].Value
} # next match
Write-Host "`tLetters you are missing to spell this work '$($MissingTiles -join '')'"
} # next word
Write-Host -------------------------------
$PlayerTiles = "OLLVE"
[hashtable]$SearchForTiles = @{}
# build regex for tiles
[string]$Regex = funBuildRegexForPlayerTiles -GivenTiles $PlayerTiles
Write-Host "Player tiles '$PlayerTiles'"
Write-Host "Regex = '$Regex'"
Write-Host
Write-Host "Matching words = "
$MatchedWords = $Dictionary -imatch $Regex | where {$_.Length -le $($PlayerTiles.Length + 1)}
[string]$MissingLetterRegex = funBuildMissingLetterRegex $PlayerTiles
foreach ($Word in $MatchedWords) {
Write-Host $Word -NoNewline
# find all the letters for which the player doesn't have a matching tile
[array]$MissingTiles = ([regex]"$MissingLetterRegex").matches($Word) | foreach {
Write-Output $_.Groups[0].Value
} # next match
Write-Host "`tLetters you are missing to spell this work '$($MissingTiles -join '')'"
} # next word
収量
To match an extra 'r': (?=^([^r]*?r){0,3}(?![^r]*?r))(?=^([^v]*?v){1,1}(?![^v]*?v))(?=^([^a]*?a){1,2}(?![^a]*?a))(?=^([^k]*?k){1,1}(?![^k]*?k))(?=^([^d]*?d){1,1}(?![^d]*?d))
To match an extra 'v': (?=^([^r]*?r){1,2}(?![^r]*?r))(?=^([^v]*?v){0,2}(?![^v]*?v))(?=^([^a]*?a){1,2}(?![^a]*?a))(?=^([^k]*?k){1,1}(?![^k]*?k))(?=^([^d]*?d){1,1}(?![^d]*?d))
To match an extra 'a': (?=^([^r]*?r){1,2}(?![^r]*?r))(?=^([^v]*?v){1,1}(?![^v]*?v))(?=^([^a]*?a){0,3}(?![^a]*?a))(?=^([^k]*?k){1,1}(?![^k]*?k))(?=^([^d]*?d){1,1}(?![^d]*?d))
To match an extra 'k': (?=^([^r]*?r){1,2}(?![^r]*?r))(?=^([^v]*?v){1,1}(?![^v]*?v))(?=^([^a]*?a){1,2}(?![^a]*?a))(?=^([^k]*?k){0,2}(?![^k]*?k))(?=^([^d]*?d){1,1}(?![^d]*?d))
To match an extra 'd': (?=^([^r]*?r){1,2}(?![^r]*?r))(?=^([^v]*?v){1,1}(?![^v]*?v))(?=^([^a]*?a){1,2}(?![^a]*?a))(?=^([^k]*?k){1,1}(?![^k]*?k))(?=^([^d]*?d){0,2}(?![^d]*?d))
Player tiles 'aardvrk'
Regex = '(?=^([^r]*?r){1,2}(?![^r]*?r))(?=^([^v]*?v){1,1}(?![^v]*?v))(?=^([^a]*?a){1,2}(?![^a]*?a))(?=^([^k]*?k){1,1}(?![^k]*?k))(?=^([^d]*?d){1,1}(?![^d]*?d))|(?=^([^r]*?r){0,3}(?![^r]*?r))(?=^([^v]*?v){1,1}(?![^v]*?v))(?=^([^a]*?a){1,2}(?![^a]*?a))(?=^([^k]*?k){1,1}(?![^k]*?k))(?=^([^d]*?d){1,1}(?![^d]*?d))|(?=^([^r]*?r){1,2}(?![^r]*?r))(?=^([^v]*?v){0,2}(?![^v]*?v))(?=^([^a]*?a){1,2}(?![^a]*?a))(?=^([^k]*?k){1,1}(?![^k]*?k))(?=^([^d]*?d){1,1}(?![^d]*?d))|(?=^([^r]*?r){1,2}(?![^r]*?r))(?=^([^v]*?v){1,1}(?![^v]*?v))(?=^([^a]*?a){0,3}(?![^a]*?a))(?=^([^k]*?k){1,1}(?![^k]*?k))(?=^([^d]*?d){1,1}(?![^d]*?d))|(?=^([^r]*?r){1,2}(?![^r]*?r))(?=^([^v]*?v){1,1}(?![^v]*?v))(?=^([^a]*?a){1,2}(?![^a]*?a))(?=^([^k]*?k){0,2}(?![^k]*?k))(?=^([^d]*?d){1,1}(?![^d]*?d))|(?=^([^r]*?r){1,2}(?![^r]*?r))(?=^([^v]*?v){1,1}(?![^v]*?v))(?=^([^a]*?a){1,2}(?![^a]*?a))(?=^([^k]*?k){1,1}(?![^k]*?k))(?=^([^d]*?d){0,2}(?![^d]*?d))'
Matching words =
AARDVARK Letters you are missing to spell this work 'A'
AARDVRKS Letters you are missing to spell this work 'S'
-------------------------------
To match an extra 'O': (?=^([^O]*?O){0,2}(?![^O]*?O))(?=^([^E]*?E){1,1}(?![^E]*?E))(?=^([^L]*?L){1,2}(?![^L]*?L))(?=^([^V]*?V){1,1}(?![^V]*?V))
To match an extra 'E': (?=^([^O]*?O){1,1}(?![^O]*?O))(?=^([^E]*?E){0,2}(?![^E]*?E))(?=^([^L]*?L){1,2}(?![^L]*?L))(?=^([^V]*?V){1,1}(?![^V]*?V))
To match an extra 'L': (?=^([^O]*?O){1,1}(?![^O]*?O))(?=^([^E]*?E){1,1}(?![^E]*?E))(?=^([^L]*?L){0,3}(?![^L]*?L))(?=^([^V]*?V){1,1}(?![^V]*?V))
To match an extra 'V': (?=^([^O]*?O){1,1}(?![^O]*?O))(?=^([^E]*?E){1,1}(?![^E]*?E))(?=^([^L]*?L){1,2}(?![^L]*?L))(?=^([^V]*?V){0,2}(?![^V]*?V))
Player tiles 'OLLVE'
Regex = '(?=^([^O]*?O){1,1}(?![^O]*?O))(?=^([^E]*?E){1,1}(?![^E]*?E))(?=^([^L]*?L){1,2}(?![^L]*?L))(?=^([^V]*?V){1,1}(?![^V]*?V))|(?=^([^O]*?O){0,2}(?![^O]*?O))(?=^([^E]*?E){1,1}(?![^E]*?E))(?=^([^L]*?L){1,2}(?![^L]*?L))(?=^([^V]*?V){1,1}(?![^V]*?V))|(?=^([^O]*?O){1,1}(?![^O]*?O))(?=^([^E]*?E){0,2}(?![^E]*?E))(?=^([^L]*?L){1,2}(?![^L]*?L))(?=^([^V]*?V){1,1}(?![^V]*?V))|(?=^([^O]*?O){1,1}(?![^O]*?O))(?=^([^E]*?E){1,1}(?![^E]*?E))(?=^([^L]*?L){0,3}(?![^L]*?L))(?=^([^V]*?V){1,1}(?![^V]*?V))|(?=^([^O]*?O){1,1}(?![^O]*?O))(?=^([^E]*?E){1,1}(?![^E]*?E))(?=^([^L]*?L){1,2}(?![^L]*?L))(?=^([^V]*?V){0,2}(?![^V]*?V))'
Matching words =
LOVER Letters you are missing to spell this work 'R'
LOVE Letters you are missing to spell this work ''
LOVES Letters you are missing to spell this work 'S'
LOVELY Letters you are missing to spell this work 'Y'
OLIVE Letters you are missing to spell this work 'I'
VOTE Letters you are missing to spell this work 'T'
概要
一致する単語を探している最初の部分では、これらのチャンクで構成された正規表現を使用しています: (?=^([^$Letter]*?$Letter){1,$($SearchForTiles[$Letter])}(?![^$Letter]*?$Letter)). これらのチャンクはすべて|or ステートメントで区切られています。
(?=ゼロ幅アサーションを開始^文字列の先頭に一致(必要な文字列のグループを作成する[^$Letter]*?探している文字以外の任意の文字に一致$Letter文字を合わせる)グループを閉じる
{グループを強制的に発生させる1少なくとも1回,と$($SearchForTiles[$Letter])プレイヤーが持っているこのタイルの総数まで}数量チェックを終了する
(?!周りを見回すを使用して、[^$Letter]*?この文字以外の任意の数の文字$Letter続いてこの手紙)見回しの終わり
)このゼロ幅アサーションの終わり 本質的にこの文字の検索の終わり
私が使用している単語で欠落している文字を検索すると、(?i)([^$($SearchForTiles.Keys -join '')])その後に各文字のこれらのチャンクが続き(?i)(?<=($Letter[^$Letter]*?){$($SearchForTiles[$Letter])})($Letter)ます。これらのチャックはすべて|or ステートメントで区切られています
(?i)大文字と小文字を区別しないようにする(グループチェック開始[^これらの文字を含まない$($SearchForTiles.Keys -join '')プレイヤー タイル セット内の重複除去された各文字を取得し、それらを結合します]文字セットの終わり)基本的に、プレーヤーのトレイにないすべての文字を返します
|or ステートメント- 続いて、プレーヤーのトレイ内の文字ごとに、このような 1 つのグループが続きます
(?i)強制的に大文字と小文字を区別しない(?<=後読みを開始(この順序でなければならない文字の開始グループ$Letterこの手紙を探して[^$Letter]この文字以外の任意の文字が続く*?ゼロ回以上)この順序でなければならない文字のグループを閉じます{$($SearchForTiles[$Letter])}欠落している文字の照合を開始する前に、そのグループはプレイヤーのトライヤのタイルごとに少なくとも 1 回存在する必要があります)後読みを閉じる
($Letter)探している文字と一致します。これが一致する場合、プレーヤーはトレイにこの文字がないため、この文字が返されます。
于 2013-05-12T04:45:35.537 に答える
0
辞書には大文字以外は含まれていないため、最も単純なオプションが最適です。
final Pattern p = Pattern.compile("AARDV.RK")`
for (String entry : dict)
if (p.matcher(entry).matches()) return entry;
return null;
ワイルドカード.は、その位置にある任意の文字と一致するため、この文字に対してあらゆる種類の重複チェックを行うというわずかなペナルティを回避できます。また、事前に正規表現をコンパイルし、エントリごとに再コンパイルしないことが非常に重要であることにも注意してください。
于 2013-05-11T20:39:31.157 に答える