leetcode

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

0127.cpp (2907B)

      1 // Make graph and search, interesting similarity test, O(n^2)
      2 class Solution {
      3     static uint64_t convert(const string &word) {
      4         uint64_t res = 0;
      5         for (const char c : word)
      6             res = (res << 5) + (c & 0x1F);
      7         return res;
      8     }
      9 
     10     static bool connected(uint64_t a, uint64_t b) {
     11         const uint64_t cmp = max(a, b) ^ min(a, b);
     12         return (63 - __builtin_clzll(cmp)) / 5 == __builtin_ctzll(cmp) / 5;
     13     }
     14 
     15   public:
     16     int ladderLength(const string &beginWord, const string &endWord, const vector<string> &wordList) const {
     17         static uint64_t val[5001];
     18         const int n = wordList.size();
     19         vector<vector<int>> adj(n + 1);
     20 
     21         for (int i = 0; i < n; i++)
     22             val[i] = convert(wordList[i]);
     23         val[n] = convert(beginWord);
     24 
     25         int m = -1;
     26         for (int i = 0; i < n; i++) {
     27             if (wordList[i] == beginWord) continue;
     28             if (wordList[i] == endWord) m = i;
     29             for (int j = i + 1; j <= n; j++) {
     30                 if (connected(val[i], val[j])) {
     31                     adj[i].push_back(j);
     32                     adj[j].push_back(i);
     33                 }
     34             }
     35         }
     36 
     37         if (m == -1) return 0;
     38 
     39         unordered_set<int> seen;
     40         queue<int> q;
     41         q.push(n);
     42         seen.insert(n);
     43         for (int lvl = 1; !q.empty(); lvl++) {
     44             for (int k = q.size(); k > 0; k--) {
     45                 const int crnt = q.front();
     46                 q.pop();
     47                 for (const int next : adj[crnt]) {
     48                     if (seen.count(next)) continue;
     49                     if (next == m) return lvl + 1;
     50                     seen.insert(next);
     51                     q.push(next);
     52                 }
     53             }
     54         }
     55 
     56         return 0;
     57     }
     58 };
     59 
     60 // Optimal solution, by trying all similar strings, O(m*n)
     61 class Solution {
     62   public:
     63     int ladderLength(const string &beginWord, const string &endWord, const vector<string> &wordList) const {
     64         const int n = wordList.size(), m = wordList[0].size();
     65         unordered_set<string> list(begin(wordList), end(wordList));
     66         unordered_set<string> seen;
     67         queue<string> q;
     68 
     69         q.push(beginWord);
     70         seen.insert(beginWord);
     71         for (int lvl = 1; !q.empty(); lvl++) {
     72             for (int k = q.size(); k > 0; k--) {
     73                 const string &crnt = q.front();
     74                 for (int i = 0; i < m; i++) {
     75                     for (int c = 'a'; c <= 'z'; c++) {
     76                         string next = crnt;
     77                         next[i] = c;
     78                         if (list.count(next) && !seen.count(next)) {
     79                             if (next == endWord) return lvl + 1;
     80                             seen.insert(next);
     81                             q.push(next);
     82                         }
     83                     }
     84                 }
     85                 q.pop();
     86             }
     87         }
     88 
     89         return 0;
     90     }
     91 };