Added 1 solution & modified 1 solution

varunu28 · varunu28 · commit 96abc5a037f9 · 2020-08-12T11:06:58.000-05:00
diff --git a/Easy/Pascal's Triangle II.java b/Easy/Pascal's Triangle II.java
@@ -1,14 +1,21 @@
 class Solution {
-    public List<Integer> getRow(int rowIndex) {
-        List<Integer> res = new ArrayList<Integer>();
-        
-        for(int i = 0;i<rowIndex+1;i++) {
-            res.add(1);
-            for(int j=i-1;j>0;j--) {
-                res.set(j, res.get(j-1) + res.get(j));
-            }
+  public List<Integer> getRow(int rowIndex) {
+    int count = 0;
+    List<Integer> list = new ArrayList<>();
+    List<Integer> prev = new ArrayList<>();
+    for (int i = 0; i <= rowIndex; i++) {
+      prev = list;
+      List<Integer> temp = new ArrayList<>();
+      for (int j = 0; j <= i; j++) {
+        if (j == 0 || j == i) {
+          temp.add(1);
         }
-        
-        return res;
+        else {
+          temp.add(prev.get(j - 1) + prev.get(j));
+        }
+      }
+      list = temp;
     }
+    return list;
+  }   
 }
diff --git a/Medium/Restore IP Address.java b/Medium/Restore IP Address.java
@@ -0,0 +1,42 @@
+class Solution {
+  public List<String> restoreIpAddresses(String s) {
+    int n = s.length();
+    LinkedList<String> segments = new LinkedList<String>();
+    List<String> output = new ArrayList<String>();
+    backtrack(s, -1, 3, output, segments, n);
+    return output;
+  }
+  
+  private void backtrack(String s, int prevPos, int dots, List<String> output, LinkedList<String> segments, int n) {
+    int maxPos = Math.min(n - 1, prevPos + 4);
+    for (int i = prevPos + 1; i < maxPos; i++) {
+      String segment = s.substring(prevPos + 1, i + 1);
+      if (isValid(segment)) {
+        segments.add(segment);
+        if (dots - 1 == 0) {
+          updateOutput(s, i, n, segments, output);
+        }
+        else {
+          backtrack(s, i, dots - 1, output, segments, n);
+        }
+        segments.removeLast();
+      }
+    }
+  }
+  
+  public void updateOutput(String s, int currPos, int n, LinkedList<String> segments, List<String> output) {
+    String segment = s.substring(currPos + 1, n);
+    if (isValid(segment)) {
+      segments.add(segment);
+      output.add(String.join(".", segments));
+      segments.removeLast();
+    }
+  }
+
+  public boolean isValid(String segment) {
+    int m = segment.length();
+    if (m > 3)
+      return false;
+    return (segment.charAt(0) != '0') ? (Integer.parseInt(segment) <= 255) : (m == 1);
+  }
+}
