Menu
I have a 2D array of random characters. I want to match specific patterns of these characters: eg: ABA, BACKA, going up/down/left/right. What is the best algorithm to find this pattern?
797
Approach: In order to find a pattern in a 2-D array using Rabin-Karp algorithm, consider an input matrix txt[m1][m2] and a pattern pat[n1][n2]. The idea is to find the hash of each columns of mat[][] and pat[][] and compare the hash values.
To perform a Binary search in the 2D array, the array needs to be sorted. Here is an unsorted 2D array is given, so applying Binary Search in an unsorted array is not possible. To apply Binary Search first the 2D array needs to be sorted in any order that itself takes (M*N)log(M*N) time.
If this is like a word-search in that you can only go one direction (once you start left, you can only continue to go left), the answer should be pretty simple, just go ahead and test every possible start location and go each direction. In the worst case this will be O(mn^2) for a n by n If you can go up/left/etc any number of times, the most obvious way is to treat the matrix like a graph and do a BFS or DFS. Depending on the size of the word and the distribution of letters, this may be too costly.
If you had multiple queries for a single matrix, both of these methods could be sped up by caching generated words in a trie-like structure with references to the original cells.
77
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
