leetcode

Solution to some Leetcode problems written in C++

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

0127.cpp (2907B)

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