Բառերի փաթեթավորում տախտակի վրա- Python լուծում

Հետադարձ, ռեկուրսիա, տողեր, գրաֆիկներ

Խնդիր

Այս խնդիրը խնդրել է Google-ը:

Ձեզ տրվում է պատահական տառերի N by M մատրիցա և բառերի բառարան: Տվյալ բառարանից գտե՛ք բառերի առավելագույն քանակը, որոնք կարելի է փաթեթավորել գրատախտակին։

Բառը համարվում է գրատախտակի վրա փաթեթավորելու հնարավորություն, եթե.

• Այն կարելի է գտնել բառարանում
• Այն կարող է կառուցվել չվերցված տառերից գրատախտակի վրա մինչ այժմ գտնված այլ բառերով
• Տառերը միմյանց կից են (ուղղահայաց և հորիզոնական, ոչ թե անկյունագծով):

Յուրաքանչյուր սալիկ կարելի է այցելել միայն մեկ անգամ ցանկացած բառով:

Օրինակ՝ հաշվի առնելով հետևյալ բառարանը.

{ 'eat', 'rain', 'in', 'rat' }

և մատրիցա:

[['e', 'a', 'n'],
 ['t', 't', 'i'],
 ['a', 'r', 'a']]

Ձեր ֆունկցիան պետք է վերադարձնի 3, քանի որ մենք կարող ենք «ուտել», «ներս» և «առնետ» բառերը դարձնել առանց դրանք միմյանց դիպչելու: Մենք կարող էինք այլընտրանքային կերպով «կերել» և «անձրև» անել, բայց դա սխալ կլիներ, քանի որ դա ընդամենը 2 բառ է:

Քայլ 1. Մեթոդաբանության բացահայտում

Մեզ խնդիր է տրվել, որտեղ մենք ունենք բազմաթիվ հնարավոր վավերական կոնֆիգուրացիաներ: Կան մի քանի պայմաններ, և մենք ցանկանում ենք այնպիսի կոնֆիգուրացիա, որը առավելագույնի հասցնի որոշակի նպատակ (այս դեպքում ցուցակի երկարությունը): Սա պետք է սկսի ձեր գլխում մի քանի զանգ հնչեցնել: Երբ մենք բախվում ենք նման պայմանների, մենք գիտենք, որ հետընթացը կբերի լուծման:

Քայլ 2. Հետընթաց

Ձեզանից նրանց համար, ովքեր ծանոթ չեն հետընթացին, դա ալգորիթմական տեխնիկա է խնդիրների ռեկուրսիվ լուծման համար: Մենք փորձում ենք լուծումներ կառուցել աստիճանաբար, մեկ-մեկ: Մենք հեռացնում ենք լուծումները, որոնք ժամանակի ցանկացած պահի չեն բավարարում խնդրի սահմանափակումները: Եթե ​​դուք ծանոթ եք էվոլյուցիոն ալգորիթմներին, ապա դա նույն սկզբունքն է:

Այսպիսով, ի՞նչ պետք է հաշվի առնենք: Նախ, մենք անցնում ենք և հավաքում նամակներ: Լուծման հաջորդ վիճակը կախված է ձեր ընտրած տառից: Եվ ձեր վերջնական կոնֆիգուրացիան կարող է պարզվել միայն յուրաքանչյուր տարբերակի միջով անցնելով: Սա նշանակում է, որ մենք ցանկանում ենք օգտագործել Depth First Search (DFS): Հետևյալը DFS-ի լավ անիմացիա է՝ ցիկլեր գտնելու համար:

Ուղղություններ գտնելը

Պարզելու հաջորդ քայլն այն է, թե ինչպես ենք մենք անցնում մատրիցով` գտնելու մեր բառերը: Հիշեք, որ մենք կարող ենք ընտրել միայն հարակից բառեր: Իսկ անկյունագծերը հարակից չեն համարվում։ Հետևաբար, եթե մեր տառը (x,y) էր, մենք կարող ենք ընտրել [(x-1,y), (x+1, y), (x, y-1), (x, y+1)] ինդեքսներից: Մենք ներկայացնում ենք մեր կոդի ուղղությունները՝ օգտագործելով

DIRECTIONS = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
]

Կառուցելով մեր Max Words ֆունկցիան

Մեր ռեկուրսիվ լուծումը ստեղծելու համար մենք ցանկանում ենք հետևել մի քանի տարբեր բաների: Մեզ ակնհայտորեն անհրաժեշտ է մեր տախտակը և դրա չափերը թույլատրված բառերի կողքին: Մենք նաև պետք է հետևենք, թե որ ինդեքսներն ենք այցելել (արժեքները չկրկնելու համար) և մեր ձևավորած ներկայիս բառը: Եվ երբ մենք ձևավորենք բառ, մենք այն կավելացնենք մեր բառերի ցանկում, այնպես որ մենք հետևում ենք նաև դրան: Եվ բնականաբար, մեզ անհրաժեշտ է ներկայիս տողերի և սյունակների ինդեքսը, որում մենք գտնվում ենք:

def max_words(board, n, m, words, visited, r, c, curr_word):

Մենք նաև ցանկանում ենք ժամանակ խնայել՝ դադարեցնելով, երբ կարող ենք: Գոյություն ունեն երկու անվավեր պայման.

if r < 0 or r >= n or c < 0 or c >= m or visited[r][c]:
        return []

և 2) Մենք գիտենք, որ անվավեր կոնֆիգուրացիաներ ենք ստանում, երբ մեր բառերի բառարանում ոչ մի բառ չի սկսվում մեր ընթացիկ բառով: Մենք սա կոդավորում ենք հետևյալ կերպ.

if not any(word.startswith(curr_word) for word in words):
        return [] #this gives our config a score of 0

Հաջորդը, մենք ունենք 2 հնարավոր պայման.

1. Ներկայիս բառը, որում մենք գտնվում ենք, գոյություն ունի բառարանում: Այս դեպքում մենք սա ավելացնում ենք մեր ցուցակին և սկսում ենք նոր բառեր փնտրել։ Քանի որ մենք մտածում ենք միայն շատ բառեր ունենալու մասին, և ոչ ավելի երկար բառեր, մենք պետք է դա անենք:
2. Մենք դեռ բառ չենք կազմել. Սա նշանակում է, որ մենք վավեր բառի արմատ ունենք: Այսպիսով, մենք շարունակում ենք կառուցել, մինչև գտնենք այն բառը, որը փնտրում ենք (կամ կհասնենք դադարեցման պայմաններին):

Այս դեպքերը ներկայացված են.

if curr_word in words:
        # A valid words has been found: terminate current word search and start a new one
        for r, row in enumerate(board):
            for c, val in enumerate(row):
                curr_word_set = max_words(board, n, m, words, visited, r, c, '')
                if len(curr_word_set) > len(max_word_set):
                    max_word_set = curr_word_set
        max_word_set.append(curr_word)
    else:
        for dr, dc in DIRECTIONS:
            curr_word_set = max_words(board, n, m, words, visited, r + dr, c + dc, curr_word)
            if len(curr_word_set) > len(max_word_set):
                max_word_set = curr_word_set

Այս ամենը միասին դնելով

Այժմ մենք պետք է հավաքենք այդ ամենը: Հենց այստեղ է օգնում պրակտիկան և ծրագրավորման փորձը: Ուշադրություն դարձրեք, թե ինչպես ենք մենք ինտեգրում սահմանափակումները և ինչպես ենք սկզբնավորում արժեքները: Ուշադրություն դարձրեք, թե ինչպես ենք մենք աշխատում առանձին-առանձին մեր մշակած շինանյութերում: Այս ամենը գալիս է բազմաթիվ խնդիրների կիրառմամբ:

Խելացի պլանի համար, որը կարող եք օգտագործել ձեր հարցազրույցների համար նայեք այս հոդվածը: Սա պարունակում է ապացուցված քայլեր, որոնք ուսանողներն օգտագործել են իրենց հարցազրույցների համար:

Մեր վերջնական լուծումը կարծես թե

DIRECTIONS = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
]

def max_words(board, n, m, words, visited, r, c, curr_word):
    if r < 0 or r >= n or c < 0 or c >= m or visited[r][c]:
        return []
    curr_word += board[r][c]
    # if no words in |words| start with |curr_word|, then return early.
    if not any(word.startswith(curr_word) for word in words):
        return []
    visited[r][c] = True
    max_word_set = []
    if curr_word in words:
        # A valid words has been found: terminate current word search and start a new one
        for r, row in enumerate(board):
            for c, val in enumerate(row):
                curr_word_set = max_words(board, n, m, words, visited, r, c, '')
                if len(curr_word_set) > len(max_word_set):
                    max_word_set = curr_word_set
        max_word_set.append(curr_word)
    else:
        for dr, dc in DIRECTIONS:
            curr_word_set = max_words(board, n, m, words, visited, r + dr, c + dc, curr_word)
            if len(curr_word_set) > len(max_word_set):
                max_word_set = curr_word_set
    visited[r][c] = False
    return max_word_set

def find_max_words(board, words):
    if not board:
        return 0
    n, m = len(board), len(board[0])
    visited = [[False for _ in range(m)] for _ in range(n)]
    max_words_so_far = []
    for r, row in enumerate(board):
        for c, val in enumerate(row):
            word_set = max_words(board, n, m, words, visited, r, c, '')
            if len(word_set) > len(max_words_so_far):
                max_words_so_far = word_set
    print(max_words_so_far)
    return len(max_words_so_far)

Քանի որ այս լուծումը իջնում ​​է բոլոր տարբեր ուղիներով, գործարկման ժամանակը էքսպոնենցիալ է:

Ավելի շատ նման լուծումների համար ստուգեք իմ Տեխնոլոգիական հարցազրույցները պարզեցված տեղեկագիրը: Tech Made Simple-ը լավագույն ռեսուրսն է այն մարդկանց համար, ովքեր ցանկանում են ստեղծել հիանալի կարիերա Tech-ում: Այն կօգնի ձեզ հայեցակարգել, կառուցել և օպտիմալացնել ձեր լուծումները: Այն ընդգրկում է ամեն ինչ՝ սկսած տեխնիկական ասպեկտներից՝ համակարգային դիզայնից, համակարգչային գիտության հայեցակարգից և Leetcode-ի խնդիրների լուծումից մինչև ցանցային կապի և ձեր կարիերան կառուցելու մանրամասն ուղեցույցներ: Խնայեք ձեր ժամանակը, ջանքերը և գումարը՝ գտնելով ձեր բոլոր կարիքները մեկ վայրում: Օգտագործեք այստեղ գտնվող հղումը՝ մինչև մեկ տարի 20% զեղչ ստանալու համար: >

Ես ստեղծեցի Տեխնոլոգիական հարցազրույցները պարզեցված՝ օգտագործելով նոր մեթոդներ, որոնք հայտնաբերվել են բազմաթիվ մարդկանց թոփ տեխնոլոգիական ընկերություններում դասավանդելու միջոցով: Տեղեկագիրը նախատեսված է ձեզ օգնելու հաջողության հասնելու համար՝ խնայելով ձեզ Leetcode grind-ի վրա վատնված ժամերից: Ես ունեմ 100% բավարարվածության քաղաքականություն, այնպես որ դուք կարող եք փորձել այն առանց ռիսկի ձեզ համար: Դուք կարող եք կարդալ ՀՏՀ-ները և ավելին իմանալ այստեղ

Ազատորեն դիմեք, եթե ունեք հետաքրքիր աշխատանք/նախագծեր/գաղափարներ նաև ինձ համար: Միշտ ուրախ եմ լսել ձեզ:

Իմ աշխատանքի դրամական աջակցության համար հետևում են իմ Venmo-ն և Paypal-ը: Ցանկացած գումար գնահատվում է և շատ է օգնում: Նվիրատվությունները բացում են բացառիկ բովանդակությունը, ինչպիսիք են թղթի վերլուծությունը, հատուկ ծածկագիրը, խորհրդատվությունները և հատուկ ուսուցումը.

Վենմո՝ https://account.venmo.com/u/FNU-Devansh

Paypal՝ paypal.me/ISeeThings

Ձեռք բերեք ինձ

Օգտագործեք ստորև բերված հղումները՝ ստուգելու իմ մյուս բովանդակությունը, ավելին իմանալու կրկնուսուցման մասին կամ պարզապես բարևելու համար: Նաև ստուգեք Robinhood-ի անվճար ուղղորդման հղումը: Մենք երկուսս էլ ստանում ենք անվճար բաժնետոմս (դուք պետք չէ որևէ գումար դնել), և ձեզ համար վտանգ չկա: Ուրեմն այն չօգտագործելը պարզապես անվճար գումար է կորցնում:

Ստուգեք իմ մյուս հոդվածները Medium-ում: : https://rb.gy/zn1aiu

Իմ YouTube-ը՝ https://rb.gy/88iwdd

Կապվեք ինձ հետ LinkedIn-ում: Եկեք միացնենք՝ https://rb.gy/m5ok2y

Իմ Instagram-ը՝ https://rb.gy/gmvuy9

Իմ Twitter-ը՝ https://twitter.com/Machine01776819

Եթե ​​պատրաստվում եք կոդավորման/տեխնիկական հարցազրույցների՝ https://codinginterviewsmadesimple.substack.com/

Ստացեք անվճար բաժնետոմս Robinhood-ում. https://join.robinhood.com/fnud75