如何查找遵循特定顺序的单词

如何查找遵循特定顺序的单词

我正在尝试编写一个脚本(script1.sh),当给定一堆字母时,该脚本可以找到每个可能的单词。

  • 这些单词必须以混乱的第一个字母开始,以最后一个字母结束。

  • 单词的字母需要遵循混乱中字母的顺序。

  • 混乱中的每个字母都可以多次使用。

所以这

./script1.sh "qwertyuytresdftyuiokn"

应该输出queenquestion不是“quieten”,因为“e”在混乱中出现在“u”和“i”之前。

我尝试将第一个、最后一个和剩余的字母分配给变量,然后使用egrep查找单词,但我找不到使用字母顺序的方法。所以这个也给了我无效的词。

#!/bin/bash

first_letter=$(echo $@ | cut -c1)
last_letter=$(echo $@ |rev| cut -c1)
remaining_letters=$(echo $@ | cut -c2- | rev | cut -c2-)

grep -E "^$first_letter[$remaining_letters]*$last_letter$" /usr/share/dict/words

然后我尝试将混乱变成数组,但我再次找不到一种方法来找到遵循混乱中顺序的单词。

答案1

#!/bin/sh
pttrn="^$(printf '%s' "$1" | sed -e 's/\(.\)/\1*/g' -e 's/\*/\\+/' -e 's/\*$/\\+/')"'$'
grep "$pttrn" /usr/share/dict/words

*通过在每个字符后注入,从第一个参数获得模式。然后第一个*改为\+;最后也是如此*。另外^$添加了 和 。您的示例输入生成以下模式:

^q\+w*e*r*t*y*u*y*t*r*e*s*d*f*t*y*u*i*o*k*n\+$

此模式是正确的模式grepq开头必须至少出现一次,n结尾必须至少出现一次。中间的每个字母可能出现零次或多次,顺序保持不变。

请注意,该脚本很愚蠢。如果您提供带有.[等输入],那么您将得到超出规范的正则表达式。提供合理的输入或扩展脚本以验证它。


例子:

$ ./script1.sh qwertyuytresdftyuiokn
queen
question
$ ./script1.sh te
tee
$ ./script1.sh superuser
seer
serer
spur
super
supper
surer
$

答案2

这是一种解决方法

首先,过滤单词列表,仅保留那些以与混杂字母相同的字母开头和结尾的单词。例如,如果混乱作为位置参数传递$1(并假设最近的bashshell)

grep -x "${1:0:1}.*${1:(-1):1}" /usr/share/dict/words

然后将这些单词中的每一个都分解成一个正则表达式 - 我想不出一个“好的”方法来做到这一点,但是使用 GNU sed 你可以这样做

$ sed -E 's/(.)\1*/+.*\1/2g' <<< "queen"
q+.*u+.*e+.*n

现在针对每个生成的模式测试混乱情况。

把它们放在一起:

$ cat script1 
#!/bin/bash

wordlist=/usr/share/dict/words

while IFS= read -r word; do 
  grep -qEx "$(sed -E 's/(.)\1*/+.*\1/2g' <<< "$word")" <<< "$1" && printf '%s\n' "$word"
done < <(grep -x "${1:0:1}.*${1:(-1):1}" "$wordlist")

然后

$ ./script1 qwertyuytresdftyuiokn
queen
question

答案3

这是另一个(在 中运行bashpython代码生成正则表达式并将其提供给grepgrep然后处理古老look实用程序的输出,该实用程序执行二分搜索以拉回示例中/usr/share/dict/words以 开头的所有单词。因此要搜索的单词集大大减少qgrep

python3 -c 'import sys
arr = list(sys.argv[1])
print(*arr, sep="*")
' $1 | grep -x -f - <(look ${1:0:1})

或者,避免使用正则表达式的look+解决方案python3

look q | ./finder.py "qwertyuytresdftyuiokn"

其中finder.py如下:

#!/usr/bin/env python3
import sys
from itertools import groupby

seek_word = sys.argv[1]
for word in sys.stdin:
    orig_word = word.strip()
    word = ''.join(k for k, g in groupby(orig_word)) 
    s_w = iter(seek_word)
    i_word = iter(word)
    if all(c in s_w for c in i_word) and not next(s_w, None):
        print(orig_word)

相关内容