-
Notifications
You must be signed in to change notification settings - Fork 22
/
FindStringInMatrix
88 lines (72 loc) · 2.99 KB
/
FindStringInMatrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*
Question: You are given a 2D array of characters and a character pattern. WAP to find if
pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered)
but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.
eg :
Matrix
{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}
Source: http://www.careercup.com/question?id=13126665
http://www.careercup.com/question?id=5890898499993600
And pattern is MICROSOFT.
*/
package FindStringInMatrix;
public class UsingPatternMatchAlgorithm {
public static void main(String[] args) {
char[][] matrix = new char[][]{{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}};
System.out.println(patternMatch(matrix, matrix.length, matrix[0].length, "MICROSOFT"));
}
public static boolean patternMatch(char[][] matrix,int rowLength,int columnLength,String pattern){
boolean found = false;
boolean[][] visited = new boolean[rowLength][columnLength]; // this will initialize visited matrix to false
outerloop:
for(int i=0;i<rowLength;i++)
for(int j=0;j<columnLength;j++){
if(findPattern(matrix, i, j, rowLength, columnLength, pattern, visited)){
found = true;
break outerloop;
}
}
return found;
}
public static boolean findPattern(char[][] matrix, int currentRow, int currentColumn,
int rowLength, int columnLength, String pattern, boolean[][] visited){
int[] rowDir = new int[]{-1, -1, -1, 0, 1, 1, 1, 0};
int[] columnDir = new int[]{1, 0, -1, -1, -1, 0, 1, 1};
/*
FOUR conditions we have to check before making the current position as VISITED
1. check whether the pattern length is 0
2. check whether the search is out of bounds
3. check whether the first character of pattern matches with the current position of matrix
4. current position is already VISITED then return false
*/
if(pattern.length()==0)
return true;
if(currentRow<0||currentRow>(rowLength-1)||currentColumn<0||currentColumn>(columnLength-1))
return false;
if(matrix[currentRow][currentColumn]!=pattern.charAt(0)||visited[currentRow][currentColumn]==true)
return false;
// If we reach here, that means that the current position in the matrix matches with the 0th position of the pattern
// i.e. matrix[currentRow][currentColumn]==pattern.charAt(0) is true here since we
// already checked previously that if this is not true then return false
visited[currentRow][currentColumn]=true;
for(int k=0;k<8;k++){
if(findPattern(matrix, currentRow+rowDir[k], currentColumn+columnDir[k], rowLength, columnLength, pattern.substring(1), visited))
return true;
}
return (visited[currentRow][currentColumn]=false);
}
}
/*
Analysis:
Time Complexity = O(m*n) since each element of the matrix is VISITED.
I think there cannot be better solution than BRUTE FORCE method.
Space Complexity = O(m*n) used by visited matrix
*/