[Java/C++] Clean Code


  • 1

    java

    class Solution {
        public int openLock(String[] deadends, String target) {
            Set<String> dead = new HashSet<>();
            for (String s : deadends) dead.add(s);
            if (dead.contains("0000")) return -1;
            if ("0000".equals(target)) return 0;
            Set<String> v = new HashSet<>();
            Queue<String> q = new LinkedList<>();
            q.add("0000");
            for (int d = 1; !q.isEmpty(); d++) {
                for (int n = q.size(); n > 0; n--) {
                    String cur = q.poll();
                    for (int i = 0; i < 4; i++) {
                        for (int dif = 1; dif <= 9; dif += 8) {
                            char[] ca = cur.toCharArray();
                            ca[i] = (char)((ca[i] - '0' + dif) % 10 + '0');
                            String s = new String(ca);
                            if (target.equals(s)) return d;
                            if (!dead.contains(s) && !v.contains(s)) q.add(s);
                            v.add(s);
                        }
                    }
                }
            }
            return -1;        
        }
    }
    

    c++

    class Solution {
    public:
        int openLock(vector<string>& deadends, string target) {
            set<string> dead(deadends.begin(), deadends.end());
            if (dead.count("0000")) return -1;
            if (target == "0000") return 0;
            set<string> v;
            queue<string> q;
            q.push("0000");
            for (int d = 1; !q.empty(); d++) {
                for (int n = q.size(); n > 0; n--) {
                    string cur = q.front(); q.pop();
                    for (int i = 0; i < 4; i++) {
                        for (int dif = 1; dif <= 9; dif += 8) {
                            string s = cur;
                            s[i] = (s[i] - '0' + dif) % 10 + '0';
                            if (s == target) return d;
                            if (!dead.count(s) && !v.count(s)) q.push(s);
                            v.insert(s);
                        }
                    }
                }
            }
            return -1;
        }
    };
    

Log in to reply
 

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