CODEWITHSUNDEEP
pythonmatrixnp
AziMez
AziMez

Reputation: 2082

Efficient way to find if a Matrix is Sub-Matrix of another one?

Given two matrices A and B.

Is there efficient or more pythonic way to find if B is a Sub-Matrix of A?

matrix

The code below is worked but I got a Time limit exceeded when the matrix is so big!

Note: The matrix data structure is represented as an array of strings.

[Input]

A=[
'7283455864',
'6731158619',
'8988242643',
'3830589324',
'2229505813',
'5633845374',
'6473530293',
'7053106601',
'0834282956',
'4607924137']

B=[
'9505',
'3845',
'3530']

[Code]

def gridSearch(G, P):
    # Write your code here
    n=len(G)    # Matrix G row number
    m=len(G[0]) # Matrix G col number

    r=len(P)    # Matrix P row number
    c=len(P[0]) # Matrix P col number

    found='NO'
    for i in range(n-r+1):
        for j in range(m-c+1):
            start_row=i
            end_row=i+r
            start_col=j
            end_col=j+c
            sub=[]
            if G[start_row][start_col]==P[0][0]:
                sub=[x[start_col:end_col] for x in G[start_row:end_row] ]
            if (sub==P):
                found='YES'
                #print(i,j)
                
    return(found)

[Expected Output]

YES

Upvotes: 2

Views: 1308

Answers (1)

itprorh66
itprorh66

Reputation: 3288

Rather than search on a letter by letter basis as you seem to be doing with your code, I would utilize the ability to search for strings within another string as follows:

def gridSearch(G, P):
    g_sze = len(G)
    p_sze = len(P)
    p_ptr = 0
    for g_ptr, g_row in enumerate(G):
        if P[p_ptr] in g_row:
            p_ptr += 1
            if p_ptr == p_sze:
                return True
        else:
            p_ptr = 0
            if g_sze - g_ptr < p_sze-p_ptr:
                return False

    return False

The above code makes use of two efficiency approaches, first it searches the arrays by rows and secondly it stops searching rows when the ability to match the remaining rows of the smaller array is no longer possible

Given your second example, here is an approach which uses the string search approach and requires column alignment.

def gridSearch2(G, P):
    g_sze = len(G)
    p_sze = len(P)
    candidates = []
    # First scan for possible start postions
    for row in range(g_sze - p_sze + 1):
        idx = 0
        while idx < g_sze - p_sze:
            ptr = G[row].find(P[0], idx)
            if ptr < 0:
                break
            candidates.append((row, ptr+idx))
            idx = idx + ptr + 1
        # test each possible start postion for matching follow on rows
        while len(candidates)  > 0:
        row, idx  = candidates.pop(0);
        rslt = True
        for pr in range(1, p_sze):
            if G[row + pr].find(P[pr], idx) != idx:
                rslt = False
                break
        if rslt:
            return True
    return False

Upvotes: 3

Related Questions