Added 1 solution & refactored 2 solutions

varunu28 · varunu28 · commit 28fa28772e98 · 2019-12-21T06:44:09.000+05:30
diff --git a/Hard/Substring with Concatenation of All Words.java b/Hard/Substring with Concatenation of All Words.java
@@ -1,41 +1,39 @@
 class Solution {
-    public List<Integer> findSubstring(String s, String[] words) {
-        List<Integer> indexes = new ArrayList<>();
-        if (words.length == 0) {
-            return indexes;
-        }
-        
-        Map<String, Integer> freqMap = new HashMap<>();
-        for (String word : words) {
-            freqMap.put(word, freqMap.getOrDefault(word, 0) + 1);
-        }
-        
-        int start = 0;
-        int oneWordLen = words[0].length();
-        int totalLen = oneWordLen * words.length;
-        
-        while ((s.length() - start) >= totalLen) {
-            String subStr = s.substring(start, start + totalLen);
-            int i = 0;
-            Map<String, Integer> map = new HashMap<>(freqMap);
-            while (i < subStr.length()) {
-                String wordStr = subStr.substring(i, i + oneWordLen);
-                
-                if (!map.containsKey(wordStr) || map.get(wordStr) < 1) {
-                    break;
-                }
-                
-                map.put(wordStr, map.get(wordStr) - 1);
-                i += oneWordLen;
-            }
-            
-            if (i >= subStr.length()) {
-                indexes.add(start);
-            }
-            
-            start++;
-        }
-        
-        return indexes;
+  public List<Integer> findSubstring(String s, String[] words) {
+    if (s.length() == 0 || words.length == 0) {
+      return new ArrayList<>();
     }
+    Map<String, Integer> wordFreqMap = new HashMap<>();
+    for (String word : words) {
+      wordFreqMap.put(word, wordFreqMap.getOrDefault(word, 0) + 1);
+    }
+    int stringLength = s.length();
+    int wordCount = words.length;
+    int singleWordLength = words[0].length();
+    List<Integer> indices = new ArrayList<>();
+    for (int i = 0; i + singleWordLength * wordCount <= stringLength; i++) {
+      if (match(s, i, singleWordLength, wordFreqMap, wordCount)) {
+        indices.add(i);
+      }
+    }
+    return indices;
+  }
+  
+  private boolean match(String s, int start, int singleWordLength, Map<String, Integer> wordFreqMap, int wordCount) {
+    Map<String, Integer> currFreqMap = new HashMap<>();
+    for (int i = 0; i < wordCount; i++) {
+      String currWord = s.substring(start + i * singleWordLength, start + (i + 1) * singleWordLength);
+      Integer freq = wordFreqMap.get(currWord);
+      // Word not in required words
+      if (freq == null) { 
+        return false;
+      }
+      currFreqMap.put(currWord, currFreqMap.getOrDefault(currWord, 0) + 1);
+      // Word occurs more than the required count
+      if (currFreqMap.get(currWord) > freq) {
+        return false;
+      }
+    }
+    return true;
+  }
 }
diff --git a/Medium/Construct Binary Search Tree from Preorder Traversal.java b/Medium/Construct Binary Search Tree from Preorder Traversal.java
@@ -0,0 +1,28 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+  int idx;
+  public TreeNode bstFromPreorder(int[] preorder) {
+    idx = 0;
+    return helper(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
+  }
+  
+  private TreeNode helper(int[] preorder, int lower, int upper) {
+    if (idx == preorder.length || preorder[idx] < lower || preorder[idx] > upper) {
+      return null;
+    }
+    int val = preorder[idx];
+    idx++;
+    TreeNode root = new TreeNode(val);
+    root.left = helper(preorder, lower, val);
+    root.right = helper(preorder, val, upper);
+    return root;
+  }
+}
diff --git a/Medium/Maximum Binary Tree.java b/Medium/Maximum Binary Tree.java
@@ -8,31 +8,35 @@
  * }
  */
 class Solution {
-    public TreeNode constructMaximumBinaryTree(int[] nums) {
-        if (nums.length == 0) {
-            return null;
-        }
-        
-        return constructTree(nums, 0, nums.length-1);
+  public TreeNode constructMaximumBinaryTree(int[] nums) {
+    if (nums.length == 0) {
+      return null;
     }
-    
-    private TreeNode constructTree(int[] nums, int start, int end) {
-        if (start > end) {
-            return null;
-        }
-        
-        int idx = start;
-        for (int i=start+1; i<=end; i++) {
-            if (nums[i] > nums[idx]) {
-                idx = i;
-            }
-        }
-        
-        TreeNode root = new TreeNode(nums[idx]);
-        
-        root.left = constructTree(nums, start, idx-1);
-        root.right = constructTree(nums, idx+1, end);
-        
-        return root;
+    TreeNode root = helper(nums, 0, nums.length - 1);
+    return root;
+  }
+  
+  private TreeNode helper(int[] nums, int start, int end) {
+    if (start > end) {
+      return null;
     }
+    int maxIdx = getMaxIdx(nums, start, end);
+    TreeNode root = new TreeNode(nums[maxIdx]);
+    root.left = helper(nums, start, maxIdx - 1);
+    root.right = helper(nums, maxIdx + 1, end);
+    return root;
+  }
+  
+  private int getMaxIdx(int[] nums, int start, int end) {
+    int maxVal = Integer.MIN_VALUE;
+    int maxIdx = -1;
+    while (start <= end) {
+      if (nums[start] > maxVal) {
+        maxVal = nums[start];
+        maxIdx = start;
+      }
+      start++;
+    }
+    return maxIdx;
+  }
 }
