在二维数组中搜索字符串python向右或向下移动

Question

我有一个包含字符串的数组，如下所示：

l = ["abc",
     "def",
     "hij",
     "klm",
     "nop",
     "qrs"]

另一个上面写着：

word = ["abc","knq","knop"]

我需要在列表中找到单词并返回相应的坐标。你知道吗

其特殊性在于搜索必须是水平的、垂直的或同时进行的。你知道吗

例如，第一个单词：

abc返回索引[(0,0)(0,1)(0,2)]

knq返回[(3,0)(4,0)(5,0)]

knop返回[(3,0)(4,0),(4,1),(4,2)]

字符串中的字符不是唯一的，我需要保存移动，例如向下移动一个字符或向右移动一个字符。 不是对角词查找器。你知道吗

Answer 1

如果你有很多单词并且重复建立这些类型的列表，我会先建立一个翻译词典：

tr = dict()
for r,w in enumerate(l):
    for c,ch in enumerate(w):
        tr[ch] = (r,c)

这样，您就可以轻松地创建具有列表理解功能的列表：

for w in word:
    res = [tr[ch] for ch in w]
    print(w)
    print(res)

输出：

abc
[(0, 0), (0, 1), (0, 2)]
knq
[(3, 0), (4, 0), (5, 0)]
knop
[(3, 0), (4, 0), (4, 1), (4, 2)]

Answer 2

我猜角色之间必须有直接的联系。将每个字符的索引保存在dict的l中，其中key是字符，value是索引元组的列表。然后可以循环遍历word中的单词，并从单词的第一个字符列表中的每个位置（向右或向下）执行类似DFS的操作。示例（按照注释）：

l = ["abc",
     "def",
     "hij",
     "klm",
     "nop",
     "qrs"]
word = ["abc","knq","knop"]

# save the indices of each character
indices = {}
for i, w in enumerate(l):
    for j, c in enumerate(w):
        indices[c] = indices.get(c, []) + [(i, j)]
def check(i, j, k, cur, w, tmp):
    # if current word matches return the list of indices
    if cur == w:
        return tmp
    # otherwise return false if we reach either end of l
    if i == len(l) or j == len(l[i]):
        return False

    # if the current position is inside l and the character maches the k'th character of w
    if l[i][j] == w[k]:
        # add the current character and appent it's position to tmp
        cur += l[i][j]
        tmp.append((i, j))
        # check the next position either right or down
        chk1 = check(i+1, j, k+1, cur, w, tmp)
        if (chk1):
            return chk1
        chk2 = check(i, j+1, k+1, cur, w, tmp)
        if (chk2):
            return chk2
    return False

# loop through each word and then through each position of the first character
for w in word:
    for idx in indices[w[0]]:
        # if word is found print the indices and break
        chk = check(idx[0], idx[1], 0, '', w, [])
        if chk:
            print(w, chk)
            break

输出

abc [(0, 0), (0, 1), (0, 2)]
knq [(3, 0), (4, 0), (5, 0)]
knop [(3, 0), (4, 0), (4, 1), (4, 2)]