Let's Code_: LeetCode Medium: Open the Lock

Saturday, January 23, 2021

LeetCode Medium: Open the Lock

Another BFS solvable problem of LeetCode!

Problem Description: https://leetcode.com/problems/open-the-lock/

Problem Approach: BFS

Time Complexity: O(1) as the custom size of state-nodes in this problem is a constant.

Solution:

//public class OpenTheLock {
//}

import java.util.*;

class State {
    String code;
    int dist;
    State(String code, int dist) {
        this.code = code;
        this.dist = dist;
    }
}

class Solution {
    public int openLock(String[] deadends, String target) {

        Set<String> visited = new HashSet<>();
        Set<String> deadendsSet = new HashSet<>();
        for (String d : deadends) {
            deadendsSet.add(d);
        }

        if ("0000".equals(target))
            return 0;
        if (deadendsSet.contains("0000"))
            return -1;

        Queue<State> q = new LinkedList<>();
        q.add(new State("0000", 0));
        visited.add("0000");
        while (!q.isEmpty()) {
            State out = q.remove();
            List<String> neighbours = getNeighbours(out.code);
            for (String n : neighbours) {
                if (!visited.contains(n) && !deadendsSet.contains(n)) {
                    if (n.equals(target))
                        return out.dist+1;
                    State neighState = new State(n, out.dist+1);
                    visited.add(n);
                    q.add(neighState);
                }
            }
        }
        return -1;
    }

    private List<String> getNeighbours(String baseState) {
        List<String> res = new ArrayList<>();
        char[] codeChar = baseState.toCharArray();
        for (int i=0; i<codeChar.length; i++) {
            String neighState = new String();

            String c = ((codeChar[i]-'0')+1)%10 + "";
            for (int idx=0; idx<codeChar.length; idx++)
                if (idx == i)
                    neighState+=c;
                else
                    neighState+=codeChar[idx];
            res.add(neighState);

            neighState = new String();
            c = ((codeChar[i]-'0')+10-1)%10 + "";
            for (int idx=0; idx<codeChar.length; idx++)
                if (idx == i)
                    neighState+=c;
                else
                    neighState+=codeChar[idx];
            res.add(neighState);
        }
        return res;
    }

}