Java verbose solution using hashmap, just do the flip step by step


  • 0

    The idea is to use hashmap to store the visited pattern of the bulbs. So you do not need to do the 4 different flips again. And the usage of set can make sure there is no duplicates.

    public int flipLights(int n, int m) {     
        StringBuilder status = new StringBuilder();
        Map<String, String[]> memo = new HashMap<>();
        for (int i = 0; i < n; i++) {
            status.append(1);
        }
        Queue<String> current = new LinkedList<>();
        current.offer(status.toString());
        for (int i = 0; i < m; i++) {
            Set<String> visited = new HashSet<>();
            while (current.peek() != null) {
                String cs = current.poll();
                if (memo.containsKey(cs)) {
                    for (int j = 0; j < 4; j++) {
                        visited.add(memo.get(cs)[j]);
                    }
                }
                else {
                    char[] c1 = cs.toCharArray();
                    char[] c2 = cs.toCharArray();
                    char[] c3 = cs.toCharArray();
                    char[] c4 = cs.toCharArray();
                    for (int j = 0; j < n; j++) {
                        c1[j] = flip(c1[j]);
                        if (j%2 == 0) {
                            c2[j] = flip(c2[j]);
                        }
                        if (j%2 == 1) {
                            c3[j] = flip(c3[j]);
                        }
                        if ( j % 3 == 0) {
                            c4[j] = flip(c4[j]);
                        }
                    }
                    StringBuilder s1 = new StringBuilder();
                    StringBuilder s2 = new StringBuilder();
                    StringBuilder s3 = new StringBuilder();
                    StringBuilder s4 = new StringBuilder();
                    for (int j = 0; j < n; j++) {
                        s1.append(c1[j]);
                        s2.append(c2[j]);
                        s3.append(c3[j]);
                        s4.append(c4[j]);
                    }
                    visited.add(s1.toString());
                    visited.add(s2.toString());
                    visited.add(s3.toString());
                    visited.add(s4.toString());
                    String[] temp = {s1.toString(),s2.toString(),s3.toString(),s4.toString()};
                    memo.put(cs, temp);
                }
            }
            for (String str: visited) {
                current.offer(str);
            }
        }
        return current.size();
    }
    private char flip(char i) {
        if (i == '1') return '0';
        else return '1';
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.