leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0752.cpp (1012B)

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