Refactored 3 solutions

varunu28 · varunu28 · commit da4655d88b71 · 2019-12-24T08:25:10.000+05:30
diff --git a/Easy/Search Insert Position.java b/Easy/Search Insert Position.java
@@ -1,25 +1,19 @@
 class Solution {
-    public int searchInsert(int[] nums, int target) {
-        return binarySearch(nums, target);
-    }
-    
-    private int binarySearch(int[] nums, int target) {
-        int left = 0;
-        int right = nums.length - 1;
-        
-        while (left <= right) {
-            int mid = (left + right) / 2;
-            if (nums[mid] == target) {
-                return mid;
-            }
-            else if (nums[mid] > target) {
-                right = mid - 1;
-            }
-            else {
-                left = mid + 1;
-            }
-        }
-        
-        return left;
+  public int searchInsert(int[] nums, int target) {
+    int low = 0;
+    int high = nums.length - 1;
+    while (low <= high) {
+      int mid = (low + high) / 2;
+      if (nums[mid] == target) {
+        return mid;
+      }
+      else if (nums[mid] > target) {
+        high = mid - 1;
+      }
+      else {
+        low = mid + 1;
+      }
     }
+    return low;
+  }
 }
diff --git a/Medium/Add and Search Word - Data structure design.java b/Medium/Add and Search Word - Data structure design.java
@@ -1,73 +1,63 @@
 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);
+  /** Initialize your data structure here. */
+  Node root;
+  public WordDictionary() {
+    root = new Node('-');
+  }
+
+  /** Adds a word into the data structure. */
+  public void addWord(String word) {
+    Node curr = root;
+    for (char c : word.toCharArray()) {
+      if (curr.children[c - 'a'] == null) {
+        curr.children[c - 'a'] = new Node(c);
+      }
+      curr = curr.children[c - 'a'];
     }
-    
-    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;
-            }
-        }
+    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) {
+    Node curr = root;
+    return searchHelper(curr, word, 0);
+  }
+  
+  private boolean searchHelper(Node curr, String word, int idx) {
+    if (idx == word.length()) {
+      return curr.isWord;
     }
-    
-    /** 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];
+    char c = word.charAt(idx);
+    if (c != '.') {
+      if (curr.children[c - 'a'] == null) {
+        return false;
+      }
+      return searchHelper(curr.children[c - 'a'], word, idx + 1);
     }
-    
-    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);
-                }
-            }
+    else {
+      boolean flag = false;
+      for (Node child : curr.children) {
+        if (child != null) {
+          flag = flag | searchHelper(child, word, idx + 1);
         }
+      }
+      return flag;
     }
+  }
 }
 
-class TrieNode {
-    TrieNode[] children;
-    boolean isWord;
-        
-    public TrieNode() {
-        children = new TrieNode[26];
-        isWord = false;
-    }
+
+class Node {
+  char c;
+  Node[] children;
+  boolean isWord;
+  
+  public Node(char c) {
+    this.c = c;
+    children = new Node[26];
+    isWord = false;
+  }
 }
 
 /**
diff --git a/Medium/Plus One Linked List.java b/Medium/Plus One Linked List.java
@@ -7,48 +7,22 @@
  * }
  */
 class Solution {
-    public ListNode plusOne(ListNode head) {
-        ListNode rev = reverse(head);
-        ListNode prev = null;
-        int carry = 1;
-        ListNode curr = rev;
-        while (curr != null) {
-            int temp = curr.val + carry;
-            if (temp > 9) {
-                carry = 1;
-                temp = temp - 10;
-            }
-            else {
-                carry = 0;
-            }
-            
-            prev = curr;
-            
-            curr.val = temp;
-            curr = curr.next;
-        }
-        
-        if (carry != 0) {
-            prev.next = new ListNode(carry);
-        }
-        
-        ListNode ans = reverse(rev);
-        
-        return ans;
+  public ListNode plusOne(ListNode head) {
+    ListNode dummy = new ListNode(0);
+    dummy.next = head;
+    ListNode notNine = dummy;
+    while (head != null) {
+      if (head.val != 9) {
+        notNine = head;
+      }
+      head = head.next;
     }
-    
-    private ListNode reverse(ListNode node) {
-        ListNode curr = node;
-        ListNode prev = null;
-        ListNode next = null;
-        
-        while (curr != null) {
-            next = curr.next;
-            curr.next = prev;
-            prev = curr;
-            curr = next;
-        }
-        
-        return prev;
+    notNine.val++;
+    notNine = notNine.next;
+    while (notNine != null) {
+      notNine.val = 0;
+      notNine = notNine.next;
     }
+    return dummy.val != 0 ? dummy : dummy.next;
+  } 
 }
