leetcode

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

0572.cpp (1317B)

      1 class Solution {
      2     bool strStr(string haystack, string needle) {
      3         int m = haystack.size(), n = needle.size();
      4         vector<int> table(needle.size(), 0);
      5 
      6         for (int len = 0, j = 1; j < n;) {
      7             if (needle[j] == needle[len])
      8                 table[j++] = ++len;
      9             else if (len)
     10                 len = table[len - 1];
     11             else
     12                 table[j++] = 0;
     13         }
     14 
     15         for (int i = 0, j = 0; i < m;) {
     16             if (haystack[i] == needle[j]) i++, j++;
     17             if (j == n) return true;
     18             if (i < m && haystack[i] != needle[j]) j ? j = table[j - 1] : i++;
     19         }
     20 
     21         return false;
     22     }
     23 
     24     string tree_preorder_string(TreeNode *root) {
     25         if (!root) return "";
     26         string res = "";
     27         stack<TreeNode *> st;
     28 
     29         st.push(root);
     30         while (!st.empty()) {
     31             TreeNode *root = st.top();
     32             st.pop();
     33             res += root ? "_" + to_string(root->val) : "#";
     34             if (!root) continue;
     35             st.push(root->right);
     36             st.push(root->left);
     37         }
     38         return res;
     39     }
     40 
     41   public:
     42     bool isSubtree(TreeNode *root, TreeNode *subRoot) {
     43         string tree = tree_preorder_string(root);
     44         string sub = tree_preorder_string(subRoot);
     45         return strStr(tree, sub);
     46     }
     47 };