leetcode

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 };