leetcode/Problems/1367.cpp at master · DimitrijeDobrota/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    vector<int> needle, lps;

    void computeKMPTable(vector<int> needle) {
        lps.resize(needle.size(), 0);

        for (int len = 0, j = 1; j < size(needle);) {
            if (needle[j] == needle[len])
                lps[j++] = ++len;
            else if (len)
                len = lps[len - 1];
            else
                lps[j++] = 0;
        }
    }

    bool kmpSearch(TreeNode *root, int j) {
        if (j == size(needle)) return true;
        if (!root) return false;
        while (j > 0 && root->val != needle[j])
            j = lps[j - 1];
        if (root->val == needle[j]) j++;
        return kmpSearch(root->left, j) || kmpSearch(root->right, j);
    }

  public:
    bool isSubPath(ListNode *head, TreeNode *root) {
        if (!head || !root) return false;

        needle.resize(0);
        for (ListNode *t = head; t; t = t->next)
            needle.push_back(t->val);

        computeKMPTable(needle);
        return kmpSearch(root, 0);
    }
};