Q16 Sliding Puzzle - LeetCode 773
Mon Apr 24 2023 04:02:05 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int slidingPuzzle(int[][] board) {
/* Q9 of graph playlist , we make a allowed swaps for every index and call bfs
for intial string and whenever initial string is equal to target string we return
that level
*/
//making a hashset of visited strings
HashSet<String> set = new HashSet<>();
String target = "123450";
//making initial string
StringBuilder sb = new StringBuilder();
for(int i = 0 ;i < board.length ; i++){
for(int j = 0 ; j < board[0].length ; j++){
sb.append(board[i][j]);
}
}
String initial = sb.toString();
//making a q and adding initial to the q
LinkedList<String> q= new LinkedList<>();
q.addLast(initial);
//make 2d array for allowed swaps for every index
int [][] swaps = {{1,3} , {0,4 ,2}, {1,5} , {0,4}, {1 ,3 ,5} , {2 , 4}};
//applying bfs and returning level
int level = 0;
while(q.size() > 0){
int size = q.size();
while(size-- > 0){
String rem = q.pop();
// System.out.println(target + "->" + rem);
if(rem.equals(target))
return level;
//find 0th index in current string
int idx = rem.indexOf('0');
// System.out.println(idx);
//applying swaps
for(int swap : swaps[idx]){
String swapped = swap(idx , swap , rem);
// System.out.println(swapped);
if(set.contains(swapped) == false){
set.add(swapped);
q.add(swapped);
}
}
}
level++;
}
return -1;
}
public String swap (int i , int j , String str){
StringBuilder sb = new StringBuilder(str);
sb.setCharAt(i , str.charAt(j));
sb.setCharAt(j , str.charAt(i));
return sb.toString();
}
}
content_copyCOPY
https://leetcode.com/problems/sliding-puzzle/
Comments