leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0752.cpp (1012B)

0 class Solution { 1 public: 2 vector<string> neighbours(const string &code) { 3 vector<string> res; 4 for (int i = 0; i < 4; i++) { 5 for (int j = -1; j <= 1; j += 2) { 6 string s = code; 7 s[i] = (code[i] - '0' + j + 10) % 10 + '0'; 8 res.push_back(s); 9 } 10 } 11 return res; 12 } 13 14 int openLock(vector<string> &deadends, string target) { 15 unordered_set<string> um(deadends.begin(), deadends.end()); 16 if (um.count("0000")) return -1; 17 18 queue<string> q({"0000"}); 19 for (int cnt = 0; !q.empty(); ++cnt) { 20 for (int i = q.size(); i > 0; --i) { 21 string s = q.front(); 22 q.pop(); 23 if (s == target) return cnt; 24 25 for (string &s : neighbours(s)) { 26 if (um.count(s)) continue; 27 um.insert(s); 28 q.push(s); 29 } 30 } 31 } 32 return -1; 33 } 34 };