November 24, 2019

Part 2.6: Leet Code Solutions For Java Coding Interview Round

Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
  • Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  • Any right parenthesis ')' must have a corresponding left parenthesis '('.
  • Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  • '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
  • An empty string is also valid.

Example 1:
Input: "()"
Output: True

Example 2:
Input: "(*)"
Output: True

Example 3:
Input: "(*))"
Output: True

Note: The string size will be in the range [1, 100].

GIT URL: Java Solution of Leet Code's Product of Valid Parenthesis String problem
Java Solution
Construct Binary Search Tree from Preorder Traversal 

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note
1 <= preorder.length <= 100
The values of preorder are distinct.

Algorithm
1). We will write a recursive function constructTree(), which will create a Binary tree from preorder. This function will take preorder, preIndex, min and max.
2). We will first construct the root node of BST which would be the first key in the preorder sequence. But before this we will check if key is greater than min (which is Integer.MIN_VALUE for root node) and less than max(which is Integer.MAX_VALUE for the root node).
3). Call the recursive function for the left sub-tree with keys in the preorder sequence that appears before the i'th index (excluding first index).

4). Call the recursive function for the right sub-tree with keys in the preorder sequence that appears after the i'th index (including i'th index)

-K Himaanshu Shuklaa..

No comments:

Post a Comment