Java Solution with tree serialization and KMP substring match


  • 0
    J

    Because java's contain method runs in worst case O(mn) time. We need to replace it with kmp substring match to achieve truely linear time solution.

    public boolean isSubtree(TreeNode s, TreeNode t) {
            String sBytes = serialize(s);
            String tBytes = serialize(t);
            return patternMatch(sBytes, tBytes);//kmp algorihm.
        }
        
        private boolean patternMatch(String s, String t) {
            int[] tempArr = buildTempArr(t);
            int idx = 0;
            for (int i = 0; i < s.length() && idx < t.length();) {
                if (s.charAt(i) == t.charAt(idx)) {
                    idx++;
                    i++;
                } else {
                    if (idx != 0) idx = tempArr[idx - 1];
                    else i++;
                }
            }
            if (idx == t.length()) return true;
            return false;
        }
        
        private int[] buildTempArr(String t) {
            int[] fixArr = new int[t.length()];
            int j = 0, i = 1;
            while (i < t.length()) {
                if (t.charAt(i) == t.charAt(j)) {
                    fixArr[i] = j + 1;
                    i++;
                    j++;
                } else {
                    if (j != 0) {
                        j = fixArr[j - 1];
                    } else {
                        fixArr[i] = 0;
                        i++;
                    }
                }
            }
            return fixArr;
        }
        
        private String serialize(TreeNode s) {
            StringBuilder sb = new StringBuilder();
            //inorder traversal
            Stack<TreeNode> stack = new Stack<>();
            stack.push(s);
            while (!stack.isEmpty()) {
                TreeNode top = stack.pop();
                if (top == null) {
                    sb.append("#");
                } else {
                    sb.append("-"+top.val+"-");
                    stack.push(top.right);
                    stack.push(top.left);
                }
            }
            return sb.toString();
        }
    

    Reference:
    https://www.youtube.com/watch?v=GTJr8OvyEVQ
    https://discuss.leetcode.com/topic/88700/easy-o-n-java-solution-using-inorder-and-preorder-traversal


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.