Tarkibga o'tish

So'z qidirish

m × n o'lchamli harflar gridi va word so'zi berilgan. So'z ketma-ket ulangan kataklar bo'ylab hosil qilinishi mumkinmi — buni aniqlang.

Katak faqat gorizontal yoki vertikal yo'nalishda qo'shni boshqa katakka ulangan. Bir xil katak bir so'zda ikki marta ishlatilishi mumkin emas.

Kirish:
  A B C E
  S F C S
  A D E E

word = "ABCCED"
Chiqish: TRUE

word = "SEE"
Chiqish: TRUE

word = "ABCB"
Chiqish: FALSE

ABCB da B ikki marta ishlatish kerak bo'ladi — bu ruxsat etilmaydi.

Asosiy g'oya: DFS va backtracking

Bu masalada bir manbadan so'zning barcha mumkin bo'lgan yo'llari tekshiriladi. Bir yo'l noto'g'ri bo'lsa — orqaga qaytib boshqa yo'l ko'riladi. Bu DFS + backtracking ning klassik qo'llanishi.

Algoritm:

  1. Gridin har katakidan so'zning birinchi harfi bilan solishtirish.
  2. Mos kelsa — shu katakdan DFS boshlash.
  3. DFS: hozirgi pozitsiya so'zning keyingi harfiga mos kelmaslik hollarda FALSE qaytarish.
  4. Mos kelsa — katakni visited belgilab, 4 yo'nalishda davom etish.
  5. So'zning barcha harflari topilsa — TRUE.
  6. DFS qaytgach — katakni visited dan olib tashlash (backtrack), boshqa yo'l uchun yana ishlatilishi mumkin.

Pseudocode

FUNCTION EXIST(grid, word)
    rows = grid qatorlar soni
    cols = grid ustunlar soni

    FOR row = 0 DAN rows - 1 GACHA
        FOR col = 0 DAN cols - 1 GACHA
            IF DFS(grid, word, row, col, 0)
                RETURN TRUE

    RETURN FALSE

FUNCTION DFS(grid, word, row, col, index)
    IF index = LENGTH(word)
        RETURN TRUE       // barcha harflar topildi

    IF row < 0 YO row >= rows
        RETURN FALSE
    IF col < 0 YO col >= cols
        RETURN FALSE
    IF grid[row][col] ≠ word[index]
        RETURN FALSE
    IF grid[row][col] = '#'   // visited belgi
        RETURN FALSE

    temp              = grid[row][col]
    grid[row][col]    = '#'          // visited deb belgilash

    found = DFS(grid, word, row + 1, col, index + 1) OR
            DFS(grid, word, row - 1, col, index + 1) OR
            DFS(grid, word, row, col + 1, index + 1) OR
            DFS(grid, word, row, col - 1, index + 1)

    grid[row][col] = temp            // backtrack: asl qiymatga qaytarish

    RETURN found

Grid qiymatini '#' ga o'zgartirish visited ni boshqaradi. DFS tugagach asl qiymat qaytariladi — orqaga qaytish (backtracking). Bu xuddi "izimni o'chirish" kabi: shu katakdan o'tgan yo'l muvaffaqiyatsiz bo'lsa, katak boshqa yo'l uchun yana mavjud.

Bosqichma-bosqich dry run

Grid:
  A B C E
  S F C S
  A D E E

word = "ABCCED"

Tashqi tsikl (0,0) dan boshlanadi: grid[0][0] = 'A' = word[0]. DFS boshlanadi.

DFS(0,0, index=0):
  grid[0][0]='A' = word[0]='A' ✓
  grid[0][0] = '#'

  DFS(1,0, index=1):  grid[1][0]='S' ≠ word[1]='B' → FALSE
  DFS(-1,0, index=1): chegaradan tashqari → FALSE
  DFS(0,1, index=1):  grid[0][1]='B' = word[1]='B' ✓
    grid[0][1] = '#'

    DFS(1,1, index=2):  grid[1][1]='F' ≠ word[2]='C' → FALSE
    DFS(-1,1, index=2): chegaradan tashqari → FALSE
    DFS(0,2, index=2):  grid[0][2]='C' = word[2]='C' ✓
      grid[0][2] = '#'

      DFS(1,2, index=3):  grid[1][2]='C' = word[3]='C' ✓
        grid[1][2] = '#'

        DFS(2,2, index=4):  grid[2][2]='E' = word[4]='E' ✓
          grid[2][2] = '#'

          DFS(3,2, index=5):  chegaradan tashqari → FALSE
          DFS(1,2, index=5):  '#' → FALSE
          DFS(2,3, index=5):  grid[2][3]='E' ≠ word[5]='D' → FALSE
          DFS(2,1, index=5):  grid[2][1]='D' = word[5]='D' ✓

            DFS(_, _, index=6): index=LENGTH(word)=6 → RETURN TRUE ✓

          → RETURN TRUE
        grid[2][2] = 'E'  // backtrack (aslida kerak emas, TRUE topildi)
        → RETURN TRUE
      grid[1][2] = 'C'
      → RETURN TRUE
    grid[0][2] = 'C'
    → RETURN TRUE
  grid[0][1] = 'B'
  → RETURN TRUE
grid[0][0] = 'A'
→ RETURN TRUE

Javob: TRUE

word = "ABCB" uchun:

DFS(0,0, index=0): 'A'='A' ✓, '#' qo'yildi
  DFS(0,1, index=1): 'B'='B' ✓, '#' qo'yildi
    DFS(0,2, index=2): 'C'='C' ✓, '#' qo'yildi
      DFS(0,1, index=3): '#' (visited) → FALSE
      DFS(0,3, index=3): 'E'≠'B' → FALSE
      DFS(1,2, index=3): 'C'≠'B' → FALSE
      DFS(-1,2, index=3): chegaradan tashqari → FALSE
      → FALSE (barcha yo'nalishlar muvaffaqiyatsiz)
    grid[0][2]='C' (backtrack)
    DFS(1,1, index=2): 'F'≠'C' → FALSE
    → FALSE
  grid[0][1]='B' (backtrack)
  ...

Barcha yo'llar tekshirilgach FALSE qaytariladi. ABCB topilmadi.

Vaqt va xotira murakkabligi

Xususiyat Qiymat Izoh
Vaqt O(m × n × 4^L) L = so'z uzunligi
Xotira O(L) Rekursiya chuqurligi so'z uzunligi

Har katak uchun DFS boshlanishi mumkin (m × n), har qadamda 4 yo'nalish ko'riladi, so'zning uzunligi L. Worst case: har qadam 4 yo'nalishning barchasi tekshiriladi. Amalda mos kelmaslik holatlari ko'p bo'lsa tezroq qaytiladi.

Xotira: alohida visited tuzilma kerak emas — grid o'zgartiriladi. Rekursiya chuqurligi so'z uzunligiga teng O(L).

Edge case'lar

So'z bitta harfdan iborat. Gridda shu harf bormi — O(m × n) tekshirish yetarli. DFS index=0 dan boshlaydi, index=1 = LENGTH(word) → darhol TRUE.

Grid bitta katak. grid[0][0] = word[0] bo'lsa va LENGTH(word) = 1 bo'lsa — TRUE. Boshqa holatda FALSE.

So'z griddan kattaroq. Agar LENGTH(word) > m × n bo'lsa, har harf kamida bir marta ishlatilishi kerak — natija FALSE. Erta tekshirish vaqtni tejaydi.

Takroriy harflar. Grid va so'zda takroriy harflar bo'lishi mumkin — backtracking bu holat uchun ham to'g'ri ishlaydi.

Birinchi harf boshqa kataklarda ham bor. Tashqi tsikl barcha katakdan boshlashni ko'radi — birinchi uchraydigan katak to'g'ri yo'l bermasa, boshqasi ko'riladi.

Warning

Grid qiymatini vaqtincha o'zgartirish (masalan '#' ga) samarali usul, lekin multi-thread muhitda xavfli. Har thread bir xil gridni o'zgartirsa race condition kelib chiqadi. Thread-safe yechimda alohida visited matritsa kerak.

Keng tarqalgan xatolar

Backtrack qilmaslik. DFS qaytgach grid qiymatini tiklmaslik — boshqa yo'llar uchun katak "occupied" bo'lib qoladi va noto'g'ri FALSE berishi mumkin.

visited ni dequeue o'rniga push paytida boshqarish. Bu BFS uchun muhim; DFS + backtracking da visited va unvisited bir DFS yo'li davomida boshqariladi, backtrack paytida tiklanadi.

Chegarani tekshirmaslik. row va col manfiy yoki grid o'lchamidan katta bo'lishi mumkin. Har rekursiv chaqiruvda chegarani tekshirish shart.

index = LENGTH(word) ni avval tekshirmaslik. Base case — so'z to'liq topildi — boshqa tekshiruvlardan oldin bo'lishi kerak. Aks holda oxirgi harfdan keyingi chegaradan tashqari pozitsiya ko'riladi.

Xulosa

So'z qidirish — DFS va backtrackingning klassik kombinatsiyasi. Har katakdan birinchi harf bilan mos kelsa DFS boshlanadi; har qadam so'zning keyingi harfiga mos kelishini tekshiradi va visited belgilab davom etadi. Yo'l muvaffaqiyatsiz tugasa — backtrack: grid qiymati tiklanib, boshqa yo'l ko'riladi.

Vaqt murakkabligi O(m × n × 4^L) — worst case, lekin amalda mos kelmaslik holatlari DFSni erta to'xtatadi. So'z qidirishdan keyingi murakkablik: Boggle (bir nechta so'z bir vaqtda qidirish) — Trie + DFS kombinatsiyasi.