Merge branch 'master' of https://github.com/PriyankaKhire/ProgrammingPracticePython

PriyankaKhire · PriyankaKhire · commit e8d5de5cbd43 · 2021-08-26T19:56:03.000-07:00
diff --git a/Blind 75/Programs/Design Add and Search Words Data Structure.py b/Blind 75/Programs/Design Add and Search Words Data Structure.py
@@ -0,0 +1,90 @@
+# Design Add and Search Words Data Structure
+# https://leetcode.com/problems/design-add-and-search-words-data-structure/
+
+class Node(object):
+    def __init__(self):
+        self.value = None
+        # key: letter value: node
+        self.next = {}
+        self.eow = False
+        
+class Trie(object):
+    def __init__(self):
+        self.head = Node()
+    
+    def createNode(self, value):
+        node = Node()
+        node.value = value
+        return node
+    
+    def add(self, word, index, node):
+        if (index == len(word)):
+            node.eow = True
+            return
+        # if letter not in node next
+        if (word[index] not in node.next):
+            newNode = self.createNode(word[index])
+            node.next[word[index]] = newNode
+        # move on to next letter
+        self.add(word, index+1, node.next[word[index]])
+    
+    def addWord(self, word):
+        self.add(word, 0, self.head)
+        self.display(self.head, [])
+    
+    def display(self, node, words):
+        if node.eow:
+            print "".join(words)
+        for key in node.next:
+            self.display(node.next[key], words+[key])
+    
+    def searchWord(self, word):
+        return self.search(self.head, word, 0)
+        
+    def search(self, node, word, index):
+        if (index == len(word)):
+            if (node.eow):
+                return True
+            return False
+        #print "checking", word[index]
+        if (word[index] != "." and (word[index] not in node.next)):
+            return False
+        # dot can match any character
+        if (word[index] == "."):
+            for key in node.next:
+                if(self.search(node.next[key], word, index+1)):
+                    return True
+        else:
+            return self.search(node.next[word[index]], word, index+1)
+        
+        
+class WordDictionary(object):
+
+    def __init__(self):
+        self.trie = Trie()
+        """
+        Initialize your data structure here.
+        """
+        
+
+    def addWord(self, word):
+        self.trie.addWord(word)
+        """
+        :type word: str
+        :rtype: None
+        """
+        
+
+    def search(self, word):
+        return self.trie.searchWord(word)
+        """
+        :type word: str
+        :rtype: bool
+        """
+        
+
+
+# Your WordDictionary object will be instantiated and called as such:
+# obj = WordDictionary()
+# obj.addWord(word)
+# param_2 = obj.search(word)
diff --git a/Blind 75/Programs/Lowest Common Ancestor of a Binary Search Tree.py b/Blind 75/Programs/Lowest Common Ancestor of a Binary Search Tree.py
@@ -0,0 +1,45 @@
+# Lowest Common Ancestor of a Binary Search Tree
+# https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
+
+# Definition for a binary tree node.
+# class TreeNode(object):
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution(object):
+    def postOrder(self, node, p, q, answer):
+        if not node:
+            return 
+        leftFound = self.postOrder(node.left, p, q, answer)
+        rightFound = self.postOrder(node.right, p, q, answer)
+        # if found in left subtree and right sub tree
+        if (leftFound and rightFound):
+            # then append to the answer
+            answer.append(node)
+            return
+        # if one of the nodes is the value
+        if (node == p or node == q):
+            # then current node is lca
+            if (leftFound or rightFound):
+                answer.append(node)
+                return
+            # else return true since we found node in the sub tree.
+            return True
+        # if we find nothing, then we just propogate the answer from the below subtree to pass it to root.Ellipsis
+        if (leftFound or rightFound):
+            return True
+        
+            
+    def lowestCommonAncestor(self, root, p, q):
+        answer = []
+        self.postOrder(root, p, q, answer)
+        return answer[0]
+        """
+        :type root: TreeNode
+        :type p: TreeNode
+        :type q: TreeNode
+        :rtype: TreeNode
+        """
+        
diff --git a/Blind 75/Programs/Validate Binary Search Tree.py b/Blind 75/Programs/Validate Binary Search Tree.py
@@ -0,0 +1,34 @@
+# Validate Binary Search Tree
+# https://leetcode.com/problems/validate-binary-search-tree/
+
+# Definition for a binary tree node.
+# class TreeNode(object):
+#     def __init__(self, val=0, left=None, right=None):
+#         self.val = val
+#         self.left = left
+#         self.right = right
+class Solution(object):
+    # inorder traversal of BST is alwasy sorted in ascending order.
+    def inOrder(self, node, traversal):
+        if not node:
+            return
+        self.inOrder(node.left, traversal)
+        traversal.append(node.val)
+        self.inOrder(node.right, traversal)
+    
+    # validate if the traversal is in ascending order or not.
+    def validate(self, traversal):
+        for i in range(1, len(traversal)):
+            if (traversal[i-1] >= traversal[i]):
+                return False
+        return True
+        
+    def isValidBST(self, root):
+        traversal = []
+        self.inOrder(root, traversal)
+        return self.validate(traversal)
+        """
+        :type root: TreeNode
+        :rtype: bool
+        """
+        
diff --git a/Blind 75/README.md b/Blind 75/README.md
@@ -278,16 +278,27 @@
         </p>
       </li>
       <li>Construct Binary Tree from Preorder and Inorder Traversal</li>
-      <li>Validate Binary Search Tree</li>
+      <li><a href="Programs/Validate Binary Search Tree.py">Validate Binary Search Tree</a>
+        <p><b>Approach</b>: Do an inorder traversal of the BST. <br/>
+          Then validate if the traversal is in ascending order or not. 
+        </p>
+      </li>
       <li><a href="Programs/Kth Smallest Element in a BST.py">Kth Smallest Element in a BST</a> 
         <p><b>Approach</b>: User inorder traversal to find the kth smallest element.
         </p>
       </li>
-      <li>Lowest Common Ancestor of BST</li>
+      <li><a href="Programs/Lowest Common Ancestor of a Binary Search Tree.py">Lowest Common Ancestor of a Binary Search Tree</a>
+        <p><b>Approach</b>: First search for the nodes in left sub tree, and right sub tree. If found return the root. <br/>
+           Don't forget to trickle the answer upwards if nothing is found. Approach similar to postOrder traversal of the tree.
+        </p>
+      </li>
       <li><a href="Programs/Implement Trie.py">Implement Trie (Prefix Tree)</a>
         <p><b>Thoughts</b>: You can also use this approach to serialise and de-serialise an n-ary tree.</p>
       </li>
-      <li>Add and Search Word</li>
+      <li><a href="Programs/Design Add and Search Words Data Structure.py">Add and Search Word</a>
+        <p><b>Approach</b>: Use trie for this.
+        </p>
+      </li>
       <li>Word Search II</li>
     </ul>
   <h2>Heap (Solved all)</h2>
