Form a word with each row(concatenation of all chars in the row). Similarly for column and diagonal. There would be 3n words. Find if the single word to be found is a substring of the 3n words. Since reverse is also possible, we might need to check the substring of the reverse of 3n words. O(n^2). We can do with O(n) space,since we can deal only with a row or column or diagonal at a time.
On Thu, Sep 17, 2009 at 2:06 AM, ankur aggarwal <ankur.mast....@gmail.com>wrote: > All of you guys must have played a game in which a 2-D Matrix of > characters is given. The goal to find words which satisfy some criteria (eg. > Names of various countries etc...) The words can > be present horizontally, vertically and > diogonally both in forward and reverse order. > This is a pretty tough problem. Lets restrict our current problem to a > single word. > Given a matrix of characters (2-D array of characters) find the number of > occurrence of a word in that matrix. The word can be present in > 1. Row > 2. Coloum > 3. Diagonally. > > In all three cases, the word can be present both in forward and reverse > manner. > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
