Added 2 solutions & modified 1 solution

varunu28 · varunu28 · commit 0089007032e1 · 2019-07-30T08:19:36.000-07:00
diff --git a/Easy/N-th Tribonacci Number.java b/Easy/N-th Tribonacci Number.java
@@ -0,0 +1,24 @@
+class Solution {
+    Integer[] memo;
+    public int tribonacci(int n) {
+        memo = new Integer[n + 1];
+        return helper(n);
+    }
+
+    private int helper(int n) {
+        if (n == 0) {
+            return 0;
+        }
+
+        if (n == 1 || n == 2) {
+            return 1;
+        }
+
+        if (memo[n] != null) {
+            return memo[n];
+        }
+
+        memo[n] = helper(n - 3) + helper(n - 2) + helper(n - 1);
+        return memo[n];
+    }
+}
diff --git a/Easy/Valid Parantheses.java b/Easy/Valid Parantheses.java
@@ -1,24 +1,28 @@
 class Solution {
+    public Map<Character, Character> map = new HashMap<Character, Character>(){{
+        put('{', '}');
+        put('[', ']');
+        put('(', ')');
+    }};
+
     public boolean isValid(String s) {
         Stack<Character> stack = new Stack<>();
-        String open = "{([";
-        String close = "})]";
-        for (int i=0;i<s.length();i++) {
-            if (open.indexOf(s.charAt(i)) != -1) {
-                stack.push(s.charAt(i));
+        for (char c : s.toCharArray()) {
+            if (map.containsKey(c)) {
+                stack.push(c);
             }
             else {
-                if (!stack.empty()) {
-                    char c = stack.pop();
-                    if (open.indexOf(c) != close.indexOf(s.charAt(i))) {
-                        return false;
-                    }
+                if (stack.isEmpty()) {
+                    return false;
                 }
-                else {
+
+                char removed = stack.pop();
+                if (map.get(removed) != c) {
                     return false;
                 }
             }
         }
-        return stack.empty();
+
+        return stack.isEmpty();
     }
 }
diff --git a/Medium/Add and Search Word - Data structure design.java b/Medium/Add and Search Word - Data structure design.java
@@ -0,0 +1,78 @@
+class WordDictionary {
+
+    /** Initialize your data structure here. */
+    TrieNode root;
+    public WordDictionary() {
+        root = new TrieNode();
+    }
+    
+    /** Adds a word into the data structure. */
+    public void addWord(String word) {
+        addToTrie(word);
+    }
+    
+    private void addToTrie(String word) {
+        TrieNode curr = root;
+        for (int i = 0; i < word.length(); i++) {
+            char c = word.charAt(i);
+            if (curr.children[c - 'a'] == null) {
+                curr.children[c - 'a'] = new TrieNode();
+            }
+            
+            curr = curr.children[c - 'a'];
+            
+            if (i == word.length() - 1) {
+                curr.isWord = true;
+            }
+        }
+    }
+    
+    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
+    public boolean search(String word) {
+        TrieNode curr = root;
+        boolean[] ans = {false};
+        helper(word, 0, curr, ans);
+        return ans[0];
+    }
+    
+    private void helper(String word, int idx, TrieNode curr, boolean[] ans) {
+        if (curr == null) {
+            return;
+        }
+        
+        if (idx == word.length()) {
+            if (curr.isWord) {
+                ans[0] = true;
+            }
+            return;
+        }
+        
+        if (word.charAt(idx) != '.') {
+            helper(word, idx + 1, curr.children[word.charAt(idx) - 'a'], ans);
+        }
+        else {
+            for (int i = 0; i < 26; i++) {
+                if (curr.children[i] != null) {
+                    helper(word, idx + 1, curr.children[i], ans);
+                }
+            }
+        }
+    }
+}
+
+class TrieNode {
+    TrieNode[] children;
+    boolean isWord;
+        
+    public TrieNode() {
+        children = new TrieNode[26];
+        isWord = false;
+    }
+}
+
+/**
+ * Your WordDictionary object will be instantiated and called as such:
+ * WordDictionary obj = new WordDictionary();
+ * obj.addWord(word);
+ * boolean param_2 = obj.search(word);
+ */
