Question

Find all possible word combinations from letters in matrix c++

Answer 1

Explanation:

The brute force way can solve the problem in O(n!), basically calculating all the permutations and checking the results in a dictionary.

✍✍✍✍I am looking for ways to improve the complexity. I can think of building a tree out of the dictionary but still checking all letters permutations is O(n!).

Answer 2

Answer:

Explanation:

Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

Example:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};

      boggle[][]   = {{'G', 'I', 'Z'},

                      {'U', 'E', 'K'},

                      {'Q', 'S', 'E'}};

     isWord(str): returns true if str is present in dictionary

                  else false.

Output:  Following words of dictionary are present

        GEEKS

        QUIZ