sandeep1001
BAN USERMy solution: First find all guards which will take O(m*n), add it to queue as you find it.
Do BFS on the elements in queue. Total time complexity will be O(m*n). Also, I am using extra result array of size m*n, so space complexity will be O(m*n). m: no of rows and n: number of columns
class Solution {
class Position {
int i;
int j;
int distance;
public Position(int i, int j, int dist) {
this.i = i;
this.j = j;
this.distance = dist;
}
public Position() {
this.i = -1;
this.j = -1;
this.distance = -1;
}
}
public static void main(String[] args) {
char[][] matrix = { { 'o', 'o', 'o', 'g', 'o' }, { 'o', 'o', 'w', 'o', 'o' }, { 'o', 'g', 'o', 'o', 'w' },
{ 'o', 'w', 'g', 'o', 'o' }, { 'w', 'o', 'o', 'o', 'g' } };
Solution sol = new Solution();
int[][] result = sol.findDistance(matrix);
if (result == null) {
System.out.println("Invalid input Matrix");
}
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[0].length; j++) {
System.out.print(result[i][j] + " ");
}
System.out.println();
}
}
public int[][] findDistance(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return null;
}
int[][] result = new int[matrix.length][matrix[0].length];
Queue<Position> q = new LinkedList<Position>();
// finding Guards location and adding into queue
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
result[i][j] = -1;
if (matrix[i][j] == 'g') {
q.offer(new Position(i, j, 0));
result[i][j] = 0;
}
}
}
while (!q.isEmpty()) {
Position p = q.poll();
// result[p.i][p.j] = p.distance;
updateNeighbors(p, matrix, q, result);
}
return result;
}
public void updateNeighbors(Position p, char[][] matrix, Queue<Position> q, int[][] result) {
int[][] indexArray = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
for (int[] index : indexArray) {
if (isValid(p.i + index[0], p.j + index[1], matrix, result)) {
result[p.i + index[0]][p.j + index[1]] = p.distance + 1;
q.offer(new Position(p.i + index[0], p.j + index[1], p.distance + 1));
}
}
}
public boolean isValid(int i, int j, char[][] matrix, int[][] result) {
if ((i < 0 || i > matrix.length - 1) || (j < 0 || j > matrix[0].length - 1) || matrix[i][j] == 'w'
|| matrix[i][j] == 'g' || result[i][j] != -1) {
return false;
}
return true;
}
}
class WordEncrypt {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String number = sc.next();
int[] numbers = new int[number.length()];
int num = Integer.parseInt(number);
for(int i=number.length() - 1; i > -1 ; i--) {
numbers[i] = num % 10;
num = num/10;
}
WordEncrypt we = new WordEncrypt();
ArrayList<LinkedList<Integer>> result = we.findWordCombination(numbers, 0);
we.printResult(result);
}
public void printResult(ArrayList<LinkedList<Integer>> result) {
for(int i=0; i < result.size(); i++) {
LinkedList<Integer> list = result.get(i);
while(!list.isEmpty()) {
System.out.print(list.pollFirst() + ", ");
}
System.out.println();
}
}
ArrayList<LinkedList<Integer>> findWordCombination(int[] numbers, int index) {
ArrayList<LinkedList<Integer>> result = new ArrayList<LinkedList<Integer>>();
if(index == numbers.length -1 ) {
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(numbers[index]);
result.add(list);
return result;
}
ArrayList<LinkedList<Integer>> tempresult = findWordCombination(numbers, index+1);
for(int i = 0; i < tempresult.size(); i++) {
LinkedList<Integer> firstlist = new LinkedList<Integer>();
firstlist.addAll(tempresult.get(i));
int character = Integer.parseInt(numbers[index] + "" + firstlist.getFirst());
firstlist.addFirst(numbers[index]);
result.add(firstlist);
if(character < 27 && character > 9) {
LinkedList<Integer> secondlist = new LinkedList<Integer>();
secondlist.addAll(tempresult.get(i));
Integer head = secondlist.pollFirst();
secondlist.addFirst(Integer.parseInt(numbers[index] +""+ head));
result.add(secondlist);
}
}
return result;
}
}
Space complexity O(1) and Time complexity O(n)
- sandeep1001 May 23, 2016