Added 1 solution & updated 1 solution

varunu28 · varunu28 · commit 83f568b7597e · 2019-07-01T17:20:34.000-07:00
diff --git a/Hard/Unique Paths III.java b/Hard/Unique Paths III.java
@@ -0,0 +1,66 @@
+class Solution {
+    int numOfPaths;
+
+    public int uniquePathsIII(int[][] grid) {
+        numOfPaths = 0;
+        if (grid.length == 0 || grid[0].length == 0) {
+            return numOfPaths;
+        }
+
+        int startX = -1;
+        int startY = -1;
+        int emptyObstacleCount = 0;
+
+        for (int i = 0; i < grid.length; i++) {
+            for (int j = 0; j < grid[i].length; j++) {
+                if (grid[i][j] == 1) {
+                    startX = i;
+                    startY = j;
+                } else if (grid[i][j] == 0) {
+                    emptyObstacleCount++;
+                }
+            }
+        }
+
+        dfsHelper(grid, startX, startY, emptyObstacleCount, 0, new boolean[grid.length][grid[0].length]);
+
+        return numOfPaths;
+    }
+
+    private void dfsHelper(int[][] grid,
+                           int startX,
+                           int startY,
+                           int emptyObstacleCount,
+                           int currObstacleCount,
+                           boolean[][] visited) {
+        if (startX < 0 ||
+                startX >= grid.length ||
+                startY < 0 ||
+                startY >= grid[0].length ||
+                visited[startX][startY] ||
+                grid[startX][startY] == -1) {
+            return;
+        }
+
+        if (grid[startX][startY] == 2) {
+            if (currObstacleCount == emptyObstacleCount) {
+                numOfPaths++;
+            }
+
+            return;
+        }
+
+        visited[startX][startY] = true;
+
+        dfsHelper(grid, startX + 1, startY, emptyObstacleCount,
+                grid[startX][startY] == 0 ? currObstacleCount + 1 : currObstacleCount, visited);
+        dfsHelper(grid, startX - 1, startY, emptyObstacleCount,
+                grid[startX][startY] == 0 ? currObstacleCount + 1 : currObstacleCount, visited);
+        dfsHelper(grid, startX, startY + 1, emptyObstacleCount,
+                grid[startX][startY] == 0 ? currObstacleCount + 1 : currObstacleCount, visited);
+        dfsHelper(grid, startX, startY - 1, emptyObstacleCount,
+                grid[startX][startY] == 0 ? currObstacleCount + 1 : currObstacleCount, visited);
+
+        visited[startX][startY] = false;
+    }
+}
diff --git a/Medium/Simplify Path.java b/Medium/Simplify Path.java
@@ -1,32 +1,46 @@
 class Solution {
     public String simplifyPath(String path) {
-        String[] splitPaths = path.split("\\/");
-        Stack<String> paths = new Stack<>();
-        for (String p : splitPaths) {
-            if (p.length() == 0 || p.equals("/") || p.equals(" ") || p.equals(".")) {
-                continue;
-            }
+        Stack<String> stack = new Stack<>();
+        StringBuilder sb = new StringBuilder();
+        int idx = 0;
+        int n = path.length();
 
-            if (p.equals("..")) {
-                if (!paths.isEmpty()) {
-                    paths.pop();
+        while (idx < n) {
+            if (path.charAt(idx) != '/') {
+                sb.append(path.charAt(idx));
+                while (idx + 1 < n && path.charAt(idx + 1) != '/') {
+                    sb.append(path.charAt(idx + 1));
+                    idx++;
                 }
+
+                if (sb.toString().equals("..")) {
+                    if (!stack.isEmpty()) {
+                        stack.pop();
+                    }
+                }
+                else if (!sb.toString().equals(".")) {
+                    stack.push(sb.toString());
+                }
+
+                sb.setLength(0);
             }
-            else {
-                paths.push(p.trim());
-            }
+
+            idx++;
         }
 
-        Stack<String> revPath = new Stack<>();
-        while (!paths.isEmpty()) {
-            revPath.push(paths.pop());
+        List<String> list = new ArrayList<>();
+        while (!stack.isEmpty()) {
+            list.add(stack.pop());
         }
 
-        StringBuilder sb = new StringBuilder();
-        while (!revPath.isEmpty()) {
-            sb.append("/").append(revPath.pop());
+        sb.append("/");
+        for (int i = list.size() - 1; i >= 0; i--) {
+            sb.append(list.get(i));
+            if (i != 0) {
+                sb.append("/");
+            }
         }
 
-        return sb.length() == 0 ? "/" : sb.toString();
+        return sb.toString();
     }
 }
