{"id":2000,"date":"2020-06-14T15:18:53","date_gmt":"2020-06-14T15:18:53","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2000"},"modified":"2022-03-28T02:32:20","modified_gmt":"2022-03-28T02:32:20","slug":"creating-words","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/creating-words\/","title":{"rendered":"Creating Words"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Back Tracking<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a matrix of characters with n<\/code> rows and m<\/code> columns, and few words. We have to find out if the words can be formed by a series of adjacent elements. Print "Yes" if words can be formed with adjacent elements else print "No".<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction<\/strong> :<\/p>\n

\n

Idea is to iterate for every character in the matrix and check if there is any adjacent character which matches with the character of word, if it does keep check for next character of the word untill the complete word is formed with adjacent characters in matrix.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Description<\/strong>:<\/p>\n

\n

We will use backtracking to solve the above problem.
\nBacktracking<\/strong> is the approach to solve the problem by testing all possible answers (by breaking the problems into subproblems). If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.
\nAs discussed above we will iterate through each character of the matrix and see if any of the character matches with the character of the word. If it matches then we will recursively check for the next character in the word if it matches. We will return true<\/strong> if all the character in the words matches, else return false<\/strong>. We also have to keep track of the checked characters so that any character must not be checked twice. If some of the subproblems (recursive calls) fails, we will mark the characters as unvisited again so we can again use them for checking.<\/p>\n<\/blockquote>\n

Algorithm<\/strong> :
\nbk()<\/strong>:<\/p>\n

    \n
  1. if index==wordsize<\/code>, return TRUE.<\/li>\n
  2. if i<0<\/code> or j=n<\/code> or j>=m<\/code>, return FALSE.<\/li>\n
  3. store the current character, temp = a[i][j]<\/code>.<\/li>\n
  4. change the current character to mark it visited or used.<\/li>\n
  5. recurvisely call bk()<\/strong> for all four adjacent cells, if any of the calls return true, assign the original character to a (a[i][j]= temp)<\/code> & return TRUE..<\/li>\n
  6. if none of the previous calls has returned true, return FALSE<\/li>\n<\/ol>\n

    Complexity Analysis :<\/h3>\n
    \n

    We are making four recursive calls each time and for every new call again 4<\/code> recursive calls . So the time complexity<\/strong> would grow exponentially! Can you guess the time complexity?<\/p>\n<\/blockquote>\n

    Solutions:<\/h3>\n\t\t\t\t\t\t