leetcode

Solution to some Leetcode problems written in C++

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

1367.cpp (1001B)

0 class Solution { 1 vector<int> needle, lps; 2 3 void computeKMPTable(vector<int> needle) { 4 lps.resize(needle.size(), 0); 5 6 for (int len = 0, j = 1; j < size(needle);) { 7 if (needle[j] == needle[len]) 8 lps[j++] = ++len; 9 else if (len) 10 len = lps[len - 1]; 11 else 12 lps[j++] = 0; 13 } 14 } 15 16 bool kmpSearch(TreeNode *root, int j) { 17 if (j == size(needle)) return true; 18 if (!root) return false; 19 while (j > 0 && root->val != needle[j]) 20 j = lps[j - 1]; 21 if (root->val == needle[j]) j++; 22 return kmpSearch(root->left, j) || kmpSearch(root->right, j); 23 } 24 25 public: 26 bool isSubPath(ListNode *head, TreeNode *root) { 27 if (!head || !root) return false; 28 29 needle.resize(0); 30 for (ListNode *t = head; t; t = t->next) 31 needle.push_back(t->val); 32 33 computeKMPTable(needle); 34 return kmpSearch(root, 0); 35 } 36 };