There are two diagonals: up-left to bottom-right and bottom-left to up- right. So, it would be 4n "words" to search for the substring.
On 17 set, 16:47, Arun <arunm...@gmail.com> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
