Added 3 solutions & modified 1 solution

varunu28 · varunu28 · commit 9ac0bd99557d · 2019-12-30T06:14:58.000-08:00
diff --git a/Easy/Replace Elements with Greatest Element on Right Side.java b/Easy/Replace Elements with Greatest Element on Right Side.java
@@ -0,0 +1,11 @@
+class Solution {
+  public int[] replaceElements(int[] arr) {
+    int maxVal = -1;
+    for (int i = arr.length - 1; i >= 0; i--) {
+      int temp = arr[i];
+      arr[i] = maxVal;
+      maxVal = Math.max(maxVal, temp);
+    }
+    return arr;
+  }
+}
diff --git a/Hard/Number of Paths with Max Score.java b/Hard/Number of Paths with Max Score.java
@@ -0,0 +1,42 @@
+class Solution {
+  int[][] dirs = {{-1, 0}, {0, -1}, {-1, -1}};
+  final int MOD = 1000000007;
+  int[][] dpSum;
+  int[][] dpCount;
+  public int[] pathsWithMaxScore(List<String> board) {
+    int numRows = board.size();
+    int numCols = board.get(0).length();
+    dpSum = new int[numRows][numCols];
+    dpCount = new int[numRows][numCols];
+    dpCount[numRows - 1][numCols - 1] = 1;
+    helper(board, numRows, numCols);
+    return new int[]{dpSum[0][0], dpCount[0][0]};
+  }
+  
+  private void helper(List<String> board, int numRows, int numCols) {
+    for (int x = numRows - 1; x >= 0; x--) {
+      for (int y = numCols - 1; y >= 0; y--) {
+        if (dpCount[x][y] == 0) {
+          continue;
+        }
+        for (int[] dir : dirs) {
+          int newX = x + dir[0];
+          int newY = y + dir[1];
+          if (newX >= 0 && newY >= 0 && board.get(newX).charAt(newY) != 'X') {
+            int tempSum = dpSum[x][y];
+            if (board.get(newX).charAt(newY) != 'E') {
+              tempSum += Character.getNumericValue(board.get(newX).charAt(newY));
+            }
+            if (tempSum > dpSum[newX][newY]) {
+              dpCount[newX][newY] = dpCount[x][y];
+              dpSum[newX][newY] = tempSum;
+            }
+            else if (tempSum == dpSum[newX][newY]) {
+              dpCount[newX][newY] = (dpCount[newX][newY] + dpCount[x][y]) % MOD;
+            }
+          }
+        }
+      }
+    }
+  }
+}
diff --git a/Medium/Deepest Leaves Sum.java b/Medium/Deepest Leaves Sum.java
@@ -0,0 +1,32 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+  Map<Integer, Integer> map;
+  int deepestLevel;
+  public int deepestLeavesSum(TreeNode root) {
+    map = new HashMap<>();
+    deepestLevel = 0;
+    helper(root, 0);
+    return map.get(deepestLevel);
+  }
+  
+  private void helper(TreeNode root, int level) {
+    if (root == null) {
+      return;
+    }
+    if (root.left == null && root.right == null) {
+      map.put(level, map.getOrDefault(level, 0) + root.val);
+      deepestLevel = Math.max(deepestLevel, level);
+      return;
+    }
+    helper(root.left, level + 1);
+    helper(root.right, level + 1);
+  }
+}
diff --git a/Medium/Find and Replace Pattern.java b/Medium/Find and Replace Pattern.java
@@ -1,34 +1,26 @@
 class Solution {
-    public static List<String> findAndReplacePattern(String[] words, String pattern) {
-        String givenPattern = getStringPattern(pattern);
-        List<String> ans = new ArrayList<>();
-
-        for (String word : words) {
-            if (getStringPattern(word).equals(givenPattern)) {
-                ans.add(word);
-            }
-        }
-
-        return ans;
+  public List<String> findAndReplacePattern(String[] words, String pattern) {
+    String patternCode = getCode(pattern);
+    List<String> list = new ArrayList<>();
+    for (String word : words) {
+      String wordCode = getCode(word);
+      if (wordCode.equals(patternCode)) {
+        list.add(word);
+      }
     }
-
-    private static String getStringPattern(String pattern) {
-        StringBuilder sb = new StringBuilder();
-        char[] chars = pattern.toCharArray();
-        int val = 0;
-        Map<Character, Integer> map = new HashMap<>();
-
-        for (char c : chars) {
-            if (!map.containsKey(c)) {
-                map.put(c, val);
-                val++;
-            }
-        }
-
-        for (int i=0; i<chars.length; i++) {
-            sb.append(map.get(chars[i]));
-        }
-
-        return sb.toString();
+    return list;
+  }
+  
+  private String getCode(String word) {
+    Map<Character, Integer> map = new HashMap<>();
+    StringBuilder sb = new StringBuilder();
+    int count = 0;
+    for (char c : word.toCharArray()) {
+      if (!map.containsKey(c)) {
+        map.put(c, count++);
+      }
+      sb.append(map.get(c));
     }
+    return sb.toString();
+  }
 }
