算法题(6)

题目：

已知一个矩阵

matrix = [ ['A', 'P', 'H', 'S'], ['U', 'L', 'O', 'A'], ['O', 'M', 'L', 'K'], ['F', 'B', 'I', 'R'], ]

在矩阵中查找多个字符串，字符串的数量可能很多

["LFK", "HMM", "RPOOI"]

对于字符串”LFK”，它由3个字符组成，’L’、’F’、’K’ 这三个字符在矩阵中的位置分别为(1,1),(3,0),(2,3) 对于这个三个字符串分别返回 LFK

True, [(1,1),(3,0),(2,3)]

HMM 矩阵中的每个字符只能被使用一次，字符M在矩阵中只有一个，因此 HMM 无法找到

False, []

RPOOI

True, [(3,3),(0,1),(1,2),(2,0),(3,2)]

分析

矩阵中的字符数量有限（全是大写字母），且每个字符只能被使用一次，由于待查的字符串数量很多，所以需要为查找建立索引

最终代码如下:

# encoding=utf-8 from collections import defaultdict def get_position(matrix, str_list): # 初始化索引 dd = defaultdict(list) for i in range(len(matrix)): for j in range(len(matrix[i])): ch = matrix[i][j] dd[ch].append((i, j)) # deal res = [] for ss in str_list: print ss curr_dd = defaultdict(int) flag = True position_list = [] for ch in ss: curr_dd[ch] += 1 if curr_dd[ch] <= len(dd[ch]): position_list.append(dd[ch][curr_dd[ch] - 1 ]) else: flag = False res.append((False, [])) break if flag: res.append((True, position_list)) return res if __name__ == '__main__': matrix = [ ['A', 'P', 'H', 'S'], ['U', 'L', 'O', 'A'], ['O', 'M', 'L', 'K'], ['F', 'B', 'I', 'R'], ] str_list = ["ISIS", "ALLAHU"] res = get_position(matrix, str_list) for item in res: print item