leetcode

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

1367.cpp (1001B)

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