ตรวจสอบคำที่เข้าใจผิดโดยใช้ JavaScript

ปัญหา

กระดาน Boggle คืออาร์เรย์ 2 มิติของอักขระแต่ละตัว เช่น −

const board = [
   ["I","L","A","W"],
   ["B","N","G","E"],
   ["I","U","A","O"],
   ["A","S","R","L"]
];

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับใน boggle board และ string และตรวจสอบว่า string นั้นเป็นการเดาที่ถูกต้องใน boggle board หรือไม่ การเดาที่ถูกต้องคือสตริงที่สามารถเกิดขึ้นได้โดยการเชื่อมต่อเซลล์ที่อยู่ติดกัน (ในแนวนอน แนวตั้ง หรือ ตามแนวทแยงมุม) โดยไม่ใช้เซลล์ที่เคยใช้ซ้ำแล้วซ้ำอีก

ตัวอย่างเช่น ในกระดานด้านบน "LINGO" และ "ILNBIA" ล้วนเป็นการเดาที่ถูกต้อง ขณะที่ "BUNGIE" และ "SINUS" จะไม่ใช้

ตัวอย่าง

ต่อไปนี้เป็นรหัส -

const board = [
   ["I","L","A","W"],
   ["B","N","G","E"],
   ["I","U","A","O"],
   ["A","S","R","L"]
];
const guess = 'BINGO';
const checkWord = (board = [], guess = '') => {
   const numRows = board.length;
   const numCols = board[0].length;
   let queue = board.reduce((acc, row, i) => {
      row.forEach((x, j) => {
         if (x === guess[0]) {
            acc.push ( { pos: {r: i, c: j} , nextIndex: 1, path: [numCols*i + j ] } );
         }
      });
      return acc;
   }, []);
   let exploreWord = (obj, queue) => {
      let allMoves = [ {r: obj.pos.r - 1, c: obj.pos.c },
      {r: obj.pos.r + 1, c: obj.pos.c },
      {r: obj.pos.r, c: obj.pos.c - 1 },
      {r: obj.pos.r, c: obj.pos.c + 1 },
      {r: obj.pos.r - 1, c: obj.pos.c - 1 },
      {r: obj.pos.r - 1, c: obj.pos.c + 1 },
      {r: obj.pos.r + 1, c: obj.pos.c - 1 },
      {r: obj.pos.r + 1, c: obj.pos.c + 1 }];
      allMoves.forEach((o) => {
         let index = numCols * o.r + o.c;
         if (o.r >= 0 && o.r < numRows && o.c >= 0 && o.c < numCols) {
            if (board[o.r][o.c] === guess[obj.nextIndex] && !obj.path.includes(index)) {
               let cloneObj = JSON.parse(JSON.stringify(obj));
               cloneObj.pos = { r: o.r, c: o.c };
               cloneObj.nextIndex += 1;
               cloneObj.path.push(index);
               queue.push(cloneObj);
            }
         }
      });
   };
   while (queue.length > 0) {
      let obj = queue.shift();
      if (obj.nextIndex === guess.length) {
         return true;
      }
      exploreWord(obj, queue);
   }
   return false;
};
console.log(checkWord(board, guess));

คำอธิบายโค้ด

ขั้นตอนที่เราทำคือ −

• เราสแกนอาร์เรย์ 2d เพื่อค้นหาการเกิดขึ้นของตัวอักษรตัวแรก

• จากนั้นเราดัน { ตำแหน่ง ดัชนี } เข้าคิว ขณะที่คิวไม่ว่าง เราเปิดออบเจกต์แรกออกมา

• จากนั้นเรามองหาทุกทิศทาง หากตัวอักษรในเซลล์ตรงกับตัวอักษรใน word และไม่ได้ใช้เซลล์ซ้ำ เราจะอัปเดต {ตำแหน่ง, ดัชนี} และต่อท้ายคิว มิฉะนั้น เราจะทิ้งวัตถุและหยุดเมื่อพบรายการที่ตรงกันหรือไม่พบทั้งหมด

ผลลัพธ์

true