1216

surajr · surajr · commit 1bfd49f0b181 · 2017-12-16T16:09:43.000-08:00
diff --git a/README.md b/README.md
@@ -139,7 +139,8 @@ Feel free to submit pull requests, add issues and be a contributer.
 | Leetcode  | [173. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/description/) | [Java](./java/BSTIterator.java)  |   O(1)     |   O(h)        |  Medium      |         |
 | Leetcode  | [220. Contains Duplicate III](https://leetcode.com/problems/contains-duplicate-iii/description/) | [Java](./java/containsNearbyAlmostDuplicate.java)  |   O(nlogk)     |   O(k)        |  Medium      |         |
 | Leetcode  | [285. Inorder Successor in BST](https://leetcode.com/problems/inorder-successor-in-bst/description/) | [Java](./java/inorderSuccessor.java)  |   O(h)     |   O(1)        |  Medium    |         |
-| Leetcode  | [298. Binary Tree Longest Consecutive Sequence](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/description/) | [Java](./java/longestConsecutive.java)  |   O(n)     |   O(n)        |  Medium    |         |
+| Leetcode  | [297. Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/) | [Java](./java/longestConsecutive.java)  |   O(n)     |   O(n)        |  Medium    |         |
+| Leetcode  | [298. Binary Tree Longest Consecutive Sequence](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/description/) | [Java](./java/serializeDeserialize.java)  |   O(n)     |   O(n)        |  Hard    |         |
 | Leetcode  | [314. Binary Tree Vertical Order Traversal](https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/) | [Java](./java/verticalOrder.java)  |   O(n)     |   O(n)        |  Medium    |         |
 | Leetcode  | [404. Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/description/) | [Java](./java/sumOfLeftLeaves.java)  |   O(n)     |   O(n)        |  Easy    |         |
 | Leetcode  | [437. Path Sum III](https://leetcode.com/problems/path-sum-iii/description/) | [Java](./java/pathSumiii.java)  |   O(n)     |   O(1)        |  Easy     |         |
@@ -167,6 +168,7 @@ Feel free to submit pull requests, add issues and be a contributer.
 | Leetcode  | [91. Decode Ways](https://leetcode.com/problems/decode-ways/description/) | [Java](./java/numDecodings.java)  | _O(n)_       | _O(n)_          |  Medium      |         |
 | Leetcode  | [152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) | [Java](./java/MaximumProductSubArray.java)  | _O(n)_       | _O(1)_          |  Medium      |         |
 | Leetcode  | [198. House Robber](https://leetcode.com/problems/house-robber/description/) | [Java](./java/rob.java)  | _O(n)_       | _O(1)_          |  Easy      |         |
+| Leetcode  | [221. Maximal Square](https://leetcode.com/problems/maximal-square/description/) | [Java](./java/maximalSquare.java)  | _O(mn)_       | _O(mn)_          |  Medium      |         |
 | Leetcode  | [264. Ugly Number II](https://leetcode.com/problems/ugly-number-ii/description/) | [Java](./java/nthUglyNumber.java)  | _O(n)_       | _O(1)_          |  Easy      |         |
 | Leetcode  | [628. Maximum Product of Three Numbers](https://leetcode.com/problems/maximum-product-of-three-numbers) | [Java](./java/MaximumProduct.java)  | _O(n)_       | _O(1)_          |  Easy      |         |
 | Leetcode  | [646. Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/description/) | [Java](./java/findLongestChain.java)  | _O(n)_       | _O(1)_          |  Easy      |         |
diff --git a/java/maximalSquare.java b/java/maximalSquare.java
@@ -0,0 +1,18 @@
+class Solution {
+    public int maximalSquare(char[][] matrix) {
+        int row = matrix.length, col = row>0 ? matrix[0].length : 0, max = 0;
+        int [][] dp = new int[row+1][col+1];
+        for(int i=1; i<=row; i++)
+        {
+            for(int j=1; j<=col; j++)
+            {
+                if(matrix[i-1][j-1]=='1')
+                {
+                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
+                    max = Math.max(max, dp[i][j]);
+                }
+            }
+        }
+        return max*max;
+    }
+}
diff --git a/java/serializeDeserialize.java b/java/serializeDeserialize.java
@@ -0,0 +1,57 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+public class Codec {
+    
+    private String splitter = ",";
+    private String nn = "X";
+
+    // Encodes a tree to a single string.
+    public String serialize(TreeNode root) {
+        StringBuilder sb = new StringBuilder();
+        serializeHelper(root, sb);
+        return sb.toString();        
+    }
+    
+    public void serializeHelper(TreeNode node, StringBuilder sb)
+    {
+        if(node == null)
+            sb.append(nn).append(splitter);
+        else
+        {
+            sb.append(node.val).append(splitter);
+            serializeHelper(node.left, sb);
+            serializeHelper(node.right, sb);           
+        }
+    }
+
+    // Decodes your encoded data to tree.
+    public TreeNode deserialize(String data) {
+        Deque<String> nodes = new LinkedList<>();
+        nodes.addAll(Arrays.asList(data.split(splitter)));
+        return buildTree(nodes);
+    }
+    
+    public TreeNode buildTree(Deque<String> nodes)
+    {
+        String val = nodes.remove();
+        if(val.equals(nn)) return null;
+        else
+        {
+            TreeNode node = new TreeNode(Integer.valueOf(val));
+            node.left = buildTree(nodes);
+            node.right = buildTree(nodes);
+            return node;
+        }
+    }
+}
+
+// Your Codec object will be instantiated and called as such:
+// Codec codec = new Codec();
+// codec.deserialize(codec.serialize(root));
