The Grid Search (HackerRank) - Python

Question

我做了几年的开发人员，但我正在练习我的算法技能。

我在HackerRank中遇到了"网格搜索"，即使我可以解决它，我也想知道这是否是一种不错的方法。

PS：我正在尝试使用简单的指令来完成大部分工作，开发整个逻辑而不是使用预构建的函数。我的目标是提高我的逻辑思维，而不是我对语言神奇方法的了解。

#!/bin/python3
import sys

t = int(input().strip())
for a0 in range(t):
    R,C = input().strip().split(' ')
    R,C = [int(R),int(C)]
    G = []
    G_i = 0
    for G_i in range(R):
       G_t = list(input().strip())
       G.append(G_t)
    r,c = input().strip().split(' ')
    r,c = [int(r),int(c)]
    P = []
    P_i = 0
    for P_i in range(r):
       P_t = list(input().strip())
       P.append(P_t)
    mIsEqual = False
    #For each line of the matrix
    for a1 in range(0,len(G) - (len(P)-1)):
        #For each column of the given line
        for a2 in range(0,len(G[a1]) - (len(P[0])-1)):
            #If the top left value of the pattern matches the current value of the matrix, try to match it
            if(P[0][0] == G[a1][a2]):
                #If the pattern 'fits' horizontally in the matrix, try to match it
                if(len(P[0]) <= (len(G[a1]) - a2)):
                    #If the pattern 'fits' vertically in the matrix, try to match it
                    if(len(P) <= (len(G) - a1)):
                        #Match every single field of the pattern to the given area of the matrix.
                        for a3 in range(0,len(P)):
                            for a4 in range(0,len(P[0])):
                                #If the fields are equal mIsEqual is true
                                if(P[a3][a4] == G[a3+a1][a4+a2]):
                                    mIsEqual = True
                                else:
                                #If the fields are not equal stop matching this area of the matrix.
                                    mIsEqual = False
                                    break
                            #If one field in a line was not equal, stop matching this area of the matrix.
                            if(mIsEqual == False):
                                break
                    #If, after matching the whole area with the pattern mIsEqual is still true, the pattern is there.
                    if(mIsEqual):
                        break
        #If the pattern was found in the previous line, no need to keep this going.
        if(mIsEqual):
            break
    if(mIsEqual == True):
        print("YES")
    else:
        print("NO")

我正在寻找任何改进此脚本的建议，或者，如果您认为这是完全错误的，那么这不是一个好方法的原因。

谢谢！

Answer 1

这在代码审查网站上更好。

所描述的算法看起来大致正确。 但是，如果您在心理上将事物分成函数，则更容易遵循。 这也会删除一些重复的代码，并且还可以减少在代码和推荐中编写相同内容所需的量。

将您编写的内容与以下未经测试的代码进行比较。 这本质上是你只写了函数，每个函数只有一个注释：

#!/bin/python3
import sys

# Read the dimensions then a matrix from stdin
def read_matrix():
    R,C = input().strip().split(' ')
    R,C = [int(R),int(C)]
    M = []
    M_i = 0
    for M_i in range(R):
       M_t = list(input().strip())
       M.append(M_t)
    return M

# See if P can be found anywhere in G.
def found_match_in(G, P):
    for a1 in range(0,len(G) - (len(P)-1)):
        for a2 in range(0,len(G[a1]) - (len(P[0])-1)):
            if found_match_at(G, P, a1, a2):
                return True
    return False

# See if P can be found in G at location (a1, a2).
def found_match_at(G, P, a1, a2):
    for a3 in range(0,len(P)):
        for a4 in range(0,len(P[0])):
            if G[a1+a3][a2+a4] != P[a3][a4]:
                return False
    return True

t = int(input().strip())
for a0 in range(t):
    G = read_matrix()
    P = read_matrix()
    if found_match_in(G, P):
        print "YES"
    else:
        print "NO"