Today I have solved the problem in javascript

 You are given an N by N matrix of random letters and a dictionary of words. Find the maximum number of words that can be packed on the board from the given dictionary.


A word is considered to be able to be packed on the board if:


It can be found in the dictionary

It can be constructed from untaken letters by other words found so far on the board

The letters are adjacent to each other (vertically and horizontally, not diagonally).

Each tile can be visited only once by any word.

For example, given the following dictionary:


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

and matrix:


[['e', 'a', 'n'],

 ['t', 't', 'i'],

 ['a', 'r', 'a']]

Your function should return 3, since we can make the words 'eat', 'in', and 'rat' without them touching each other. We could have alternatively made 'eat' and 'rain', but that would be incorrect since that's only 2 words.


const dictionary = ['eat', 'rain', 'in', 'rat'];

const matrix = [

    ['e', 'a', 'n'],

    ['t', 't', 'i'],

    ['a', 'r', 'a']

];

function maxWords(matrix, dictionary) {

    const rows = matrix.length;

    const cols = matrix[0].length;

    const visited = Array.from({ length: rows }, () => Array(cols).fill(false));


    function canFormWord(word, row, col, index) {

        if (index === word.length) {

            return true;

        }


        if (

            row < 0 ||

            row >= rows ||

            col < 0 ||

            col >= cols ||

            visited[row][col] ||

            matrix[row][col] !== word[index]

        ) {

            return false;

        }


        visited[row][col] = true;


        const found =

            canFormWord(word, row + 1, col, index + 1) ||

            canFormWord(word, row - 1, col, index + 1) ||

            canFormWord(word, row, col + 1, index + 1) ||

            canFormWord(word, row, col - 1, index + 1);


        visited[row][col] = false;


        return found;

    }


    function countWordsFromMatrix(word) {

        let count = 0;

        for (let i = 0; i < rows; i++) {

            for (let j = 0; j < cols; j++) {

                if (!visited[i][j] && canFormWord(word, i, j, 0)) {

                    count++;

                }

            }

        }

        return count;

    }


    let maxWordCount = 0;

    for (const word of dictionary) {

        const wordCount = countWordsFromMatrix(word);

        maxWordCount = Math.max(maxWordCount, wordCount);

    }


    return maxWordCount;

}




const result = maxWords(matrix, dictionary);

console.log(result); 

Output:

1



Comments

Post a Comment

Popular posts from this blog

Building a Full-Stack Student Management System with React.js and NestJS

  🚀 My Journey Creating a Student Management System 🌟 I'm excited to share my recent project — a Student Management System ! This project gave me hands-on experience in building a full-stack application, enhancing both my frontend and backend development skills. 💡 Project Overview The Student Management System is designed to help educational institutions efficiently manage student data, including enrollment, attendance, and performance. The goal was to create a user-friendly platform for both students and administrators. 🔨 Tech Stack Used ✅ Frontend: JavaScript, HTML, CSS, React.js ✅ Backend: TypeScript, NestJS, Node.js ✅ Database: MongoDB (with _id for unique identifiers) 🌟 Key Features ✔️ Student Registration – Easy registration with unique ID management ✔️ Attendance Tracking – Real-time updates on student attendance ✔️ Performance Reports – Generate and view student performance reports ✔️ Admin Panel – Secure access for administrators to manage student...
Read more

Today I have solved the problem in javascript

 Consider the following scenario: there are N mice and N holes placed at integer points along a line. Given this, find a method that maps mice to holes such that the largest number of steps any mouse takes is minimized.Each move consists of moving one mouse one unit to the left or right, and only one mouse can fit inside each hole.For example, suppose the mice are positioned at [1, 4, 9, 15], and the holes are located at [10, -5, 0, 16]. In this case, the best pairing would require us to send the mouse at 1 to the hole at -5, so our function should return 6. const mice = [1, 4, 9, 15]; const holes = [10, -5, 0, 16]; function minSteps(mice, holes) {    mice.sort((a, b) => a - b);     holes.sort((a, b) => a - b); let maxSteps = 0;     for (let i = 0; i < mice.length; i++) {         let steps = Math.abs(mice[i] - holes[i]);         if (steps > maxSteps) {             maxStep...
Read more

Today I have solved problem in javascript

 You are given an array X of floating-point numbers x1, x2, ... xn. These can be rounded up or down to create a corresponding array Y of integers y1, y2, ... yn. Write an algorithm that finds an appropriate Y array with the following properties: The rounded sums of both arrays should be equal. The absolute pairwise difference between elements is minimized. In other words, |x1- y1| + |x2- y2| + ... + |xn- yn| should be as small as possible. For example, suppose your input is [1.3, 2.3, 4.4]. In this case you cannot do better than [1, 2, 5], which has an absolute difference of |1.3 - 1| + |2.3 - 2| + |4.4 - 5| = 1. const inputArray = [1.3, 2.3, 4.4]; const resultArray = roundArray(inputArray); function roundArray(inputArray) {     const n = inputArray.length;     const roundedArray = [];     let roundedSum = 0; for (let i = 0; i < n; i++) {         consat roundedValue = Math.round(inputArray[i]);         rounded...
Read more