leetcode

Solution to some Leetcode problems written in C++

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

0572.cpp (1317B)

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