Refactored 4 solutions

varunu28 · varunu28 · commit ece674fa90fc · 2019-12-31T06:18:57.000-08:00
diff --git a/Easy/Closest Binary Search Tree Value.java b/Easy/Closest Binary Search Tree Value.java
@@ -8,29 +8,26 @@
  * }
  */
 class Solution {
-    int ans = 0;
+  public int closestValue(TreeNode root, double target) {
+    int[] ans = {0};
     double minDiff = Double.MAX_VALUE;
-    
-    public int closestValue(TreeNode root, double target) {
-        updateVal(root, target);    
-        return ans;
+    helper(root, target, ans, minDiff);
+    return ans[0];
+  }
+  
+  private void helper(TreeNode root, double target, int[] ans, double minDiff) {
+    if (root == null) {
+      return;
     }
-    
-    private void updateVal(TreeNode root, double target) {
-        if (root == null) {
-            return;
-        }
-        
-        if (Math.abs(root.val - target) < minDiff) {
-            minDiff = Math.abs(root.val - target);
-            ans = root.val;
-        }
-        
-        if (root.val < target) {
-            updateVal(root.right, target);
-        }
-        else {
-            updateVal(root.left, target);
-        }
+    if (Math.abs(root.val - target) < minDiff) {
+      minDiff = Math.abs(root.val - target);
+      ans[0] = root.val;
     }
+    if (root.val < target) {
+      helper(root.right, target, ans, minDiff);
+    }
+    else {
+      helper(root.left, target, ans, minDiff);
+    }
+  }
 }
diff --git a/Easy/Goat Latin.java b/Easy/Goat Latin.java
@@ -1,24 +1,19 @@
 class Solution {
-    public static String toGoatLatin(String S) {
-    	
-    	StringBuilder sb = new StringBuilder("");
-    	String[] strs = S.split("\\s+");
-    	
-    	String vowels = "aeiou";
-    	StringBuilder suffix = new StringBuilder("a");
-    	
-    	for (String s : strs) {
-    		if (vowels.indexOf(s.toLowerCase().charAt(0)) != -1) {
-    			sb.append(s).append("ma").append(suffix).append(" ");
-    		}
-    		else {
-    			sb.append(s.substring(1, s.length())).append(s.charAt(0)).append("ma").append(suffix).append(" ");
-    		}
-    		
-    		suffix.append("a");
-    	}
-        
-        return sb.toString().trim();
+  public String toGoatLatin(String S) {
+    StringBuilder addAString = new StringBuilder("a");
+    StringBuilder sb = new StringBuilder();
+    Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
+    String[] strs = S.split("\\s+");
+    for (int i = 0; i < strs.length; i++) {
+      if (vowels.contains(Character.toLowerCase(strs[i].charAt(0)))) {
+        sb.append(strs[i]);
+      }
+      else {
+        sb.append(strs[i].substring(1)).append(strs[i].charAt(0));
+      }
+      sb.append("ma").append(addAString.toString()).append(" ");
+      addAString.append("a");
     }
+    return sb.toString().trim();
+  }
 }
-
diff --git a/Easy/Monotonic Array.java b/Easy/Monotonic Array.java
@@ -1,16 +1,25 @@
 class Solution {
-    public boolean isMonotonic(int[] A) {
-        if (A.length <= 2) return true;
-        boolean pattern = A[A.length-1] > A[0] ? true : false;
-        
-        for (int i=1; i<A.length; i++) {
-            if (A[i] < A[i-1] && pattern == true) {
-                return false;
-            }
-            if (A[i] > A[i-1] && pattern == false) {
-                return false;
-            }
-        }
-        return true;
+  public boolean isMonotonic(int[] A) {
+    if (A.length <= 1) {
+      return true;
     }
+    int dir = 0;
+    int idx = 0;
+    while (idx < A.length - 1 && dir == 0) {
+      dir = getDir(A, idx);
+      idx++;
+    }
+    while (idx < A.length - 1) {
+      int tempDir = getDir(A, idx);
+      if (tempDir != 0 && tempDir != dir) {
+        return false;
+      }
+      idx++;
+    }
+    return true;
+  }
+  
+  private int getDir(int[] A, int idx) {
+    return A[idx] < A[idx + 1] ? -1 : (A[idx] > A[idx + 1] ? 1 : 0);
+  }
 }
diff --git a/Easy/Verifying an Alien Dictionary.java b/Easy/Verifying an Alien Dictionary.java
@@ -1,33 +1,30 @@
 class Solution {
-    public boolean isAlienSorted(String[] words, String order) {
-        Map<Character, Integer> orderMap = new HashMap<>();
-        for (int i=0; i<order.length(); i++) {
-            orderMap.put(order.charAt(i), i);
-        }
-        
-        String prev = null;
-        
-        for (String word : words) {
-            if (prev == null) {
-                prev = word;
-                continue;
-            }
-            
-            for (int i=0; i<Math.min(prev.length(), word.length()); i++) {
-                if (orderMap.get(word.charAt(i)) > orderMap.get(prev.charAt(i))) {
-                    break;
-                }
-                else if (orderMap.get(word.charAt(i)) < orderMap.get(prev.charAt(i))) {
-                    return false;
-                } 
-                else if (word.length() != prev.length() && i == word.length() - 1) {
-                    return false;
-                }
-            }
-            
-            prev = word;
-        }
-        
+  public boolean isAlienSorted(String[] words, String order) {
+    Map<Character, Integer> map = new HashMap<>();
+    for (int i = 0; i < order.length(); i++) {
+      map.put(order.charAt(i), i);
+    }
+    for (int i = 0; i < words.length - 1; i++) {
+      if (!verifyHelper(words[i], words[i + 1], map)) {
+        return false;
+      }
+    }
+    return true;
+  }
+  
+  private boolean verifyHelper(String s1, String s2, Map<Character, Integer> map) {
+    int idx1 = 0;
+    int idx2 = 0;
+    while (idx1 < s1.length() && idx2 < s2.length()) {
+      if (map.get(s1.charAt(idx1)) < map.get(s2.charAt(idx2))) {
         return true;
+      }
+      if (map.get(s1.charAt(idx1)) > map.get(s2.charAt(idx2))) {
+        return false;
+      }
+      idx1++;
+      idx2++;
     }
+    return s1.length() <= s2.length();
+  }
 }
