นับจำนวนสตริงที่กำหนดในอาร์เรย์ตัวอักษร 2D ด้วย C++

ปัญหานี้เป็นตัวอย่างของปริศนาคำไขว้ในหนังสือพิมพ์รายวัน เราได้รับอาร์เรย์ตัวอักษร 2 มิติ และโจทย์คือการหาคำที่กำหนดจากอาร์เรย์ตัวอักษร 2 มิติ อัลกอริธึมการค้นหารวมถึงการหาตัวอักษรแต่ละตัวจาก บนลงล่าง, ขวาไปซ้าย และในทางกลับกัน แต่ไม่ได้ค้นหาแบบเฉียง

ทำความเข้าใจด้วยตัวอย่าง

Input- String word = LAYS

2D String[] = { "LOAPYS", "KAYSOT", "LAYSST", "MLVAYS", "LAYSAA", "LAOYLS" };

Output- จำนวนสตริงที่กำหนดในอาร์เรย์ตัวอักษร 2D: 7

คำอธิบาย - เราได้รับอาร์เรย์สตริงของคำ และจากนั้นเราต้องหาคำว่า "LAYS" ซึ่งสามารถค้นหาได้ในทิศทางใดก็ได้ เช่น ซ้ายไปขวา, ขวาไปซ้าย, ล่างขึ้นบน, และบนลงล่าง ตัวนับในโค้ดจะเพิ่มขึ้นทุกครั้งที่พบสตริงค้นหา และส่งคืนจำนวนนับในที่สุด ในตัวอย่างนี้ เราสามารถเห็นได้ว่า LAYS ถูกสร้างขึ้น 7 ครั้ง คือ

1 → LOAPYS -LAYS- → ซ้ายไปขวา

2 → SAYAOL -LAYS (ขวาไปซ้าย)

3 → LAYSST -LAYS (ซ้ายไปขวา)

4 → MLVAYS -LAYS (ซ้ายไปขวา)

5 → LAYSAA -LAYS (ซ้ายไปขวา)

6 → LAOYLS -LAYS (ซ้ายไปขวา)

7 → (ล่างขึ้นบน) ในสีแดง LAYS

Input- String word = CAMP

2D String[] = { "BLOOKS", "BPOOLK", "KOHPKB", "BOLKOK", "LKIOOB", "LAHYBL" }

Output- จำนวนสตริงที่กำหนดในอาร์เรย์ตัวอักษร 2D: 0

คำอธิบาย - เราได้รับอาร์เรย์สตริงของคำ และจากนั้นเราต้องหาคำว่า "LAYS" ซึ่งสามารถค้นหาได้ในทิศทางใดก็ได้ เช่น บนลงล่าง, ขวาไปซ้าย, ล่างขึ้นบน, และซ้ายไปขวา ตัวนับในโค้ดจะเพิ่มขึ้นทุกครั้งที่พบสตริงค้นหา และส่งคืนจำนวนนับในที่สุด ในตัวอย่างนี้ เราสามารถเห็นได้ว่า BOOK ถูกสร้างขึ้น 0 ครั้ง

แนวทางที่ใช้ในโปรแกรมด้านล่าง

• เราได้รับ String (word) และ String array ซึ่งร่วมกับตัวแปรยูทิลิตี้บางตัวถูกส่งเข้า findString() เพื่อประมวลผลต่อไป
• ตัวอักษรในเมทริกซ์จะถูกเดินทางผ่านและเลือกตัวอักษรหนึ่งตัวเพื่อเริ่มต้นสตริง
• สำหรับตัวอักษรที่ถูกเลือก เราจะค้นหาสตริงที่กำหนดแบบเรียกซ้ำ (recursively) ในทิศทางที่เป็นไปได้ทั้งหมดตามอัลกอริธึม
• หากพบการจับคู่ ตัวนับจะถูกเพิ่มขึ้น
• หลังจากที่เราทำเสร็จกับตัวอักษรเริ่มต้นตัวแรก กระบวนการจะทำซ้ำสำหรับตัวอักษรถัดไป
• ผลรวมของจำนวนนับจะถูกคำนวณกับการจับคู่ที่เกี่ยวข้อง
• คำตอบสุดท้ายจะถูกบันทึก และผลลัพธ์จะถูกพิมพ์

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 

int utilitySearch(string word, int r, int c, string arr[], int maxR, int maxC, int index) { 
    int count = 0; 
    if (r >= 0 && r <= maxR && c >= 0) { 
        if (c <= maxC && word[index] == arr[r][c]) { 
            char res = word[index]; 
            index = index + 1; 
            arr[r][c] = 0; 
            if (word[index] == 0) { 
                count = 1; 
            } else { 
                count = count + utilitySearch(word, r, c + 1, arr, maxR, maxC, index); 
                count = count + utilitySearch(word, r, c - 1, arr, maxR, maxC, index); 
                count = count + utilitySearch(word, r + 1, c, arr, maxR, maxC, index); 
                count = count + utilitySearch(word, r - 1, c, arr, maxR, maxC, index); 
            } 
            arr[r][c] = res; 
        } 
    } 
    return count; 
} 

int findString(string word, int r, int c, string str[], int countR, int countC) { 
    int count = 0; 
    for (int i = 0; i < countR; ++i) { 
        for (int j = 0; j < countC; ++j) { 
            count = count + utilitySearch(word, i, j, str, countR - 1, countC - 1, 0); 
        } 
    } 
    return count; 
} 

int main() { 
    string word = "FLOOD"; 
    string inp[] = {"FPLIOKOD","FLOODYUT","YFLOODPU","FMLOSODT","FILPOYOD", "FLOOOODE" }; 
    string str[(sizeof(inp) / sizeof(*inp))]; 
    for (int i = 0; i < (sizeof(inp) / sizeof(*inp)); ++i) { 
        str[i] = inp[i]; 
    } 
    cout << "Count of number of given string in 2D character array: " << findString(word, 0, 0, str, (sizeof(inp) / sizeof(*inp)), str[0].size()); 
    return 0; 
}

หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Count of number of given string in 2D character array: 6