Added solution for min adjacent swaps and serder binary tree.

anxious-coder-lhs · anxious-coder-lhs · commit 172ed3109063 · 2020-11-01T01:47:00.000+05:30
diff --git a/README.md b/README.md
@@ -57,6 +57,7 @@ Happy to accept any contributions to this in any langugage.
 ## Hard
 1. [Find Missing Positive](https://leetcode.com/problems/first-missing-positive/) | [Solution](./level_hard/LeetCode_41_Hard.ts)
 2. [Read N Characters Given Read 4 II - Call Multiple Times - LeetCode 158](https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/) | [Solution 1](./level_hard/LeetCode_158_Hard.java) | [Solution 2 Optimized](./level_hard/LeetCode_158_Hard_1.java)
+3. [Serialize Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) | [Solution](./level_hard/SerializeDeserializeBinaryTree.ts)
 
 ## Sorting
 1. Bubble Sort | [Solution](./sorting/Sort_Bubble.js)
diff --git a/level_hard/SerializeDeserializeBinaryTree.ts b/level_hard/SerializeDeserializeBinaryTree.ts
@@ -0,0 +1,76 @@
+/**
+ * Definition for a binary tree node.
+ * class TreeNode {
+ *     val: number
+ *     left: TreeNode | null
+ *     right: TreeNode | null
+ *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
+ *         this.val = (val===undefined ? 0 : val)
+ *         this.left = (left===undefined ? null : left)
+ *         this.right = (right===undefined ? null : right)
+ *     }
+ * }
+ */
+
+ /**
+  * Solution uses the depth 1st approach to solve the problem. We use a delimeter string so that multi digit
+  * values can be treated as a single entity. Further, we can also use the breadth 1st approach. Although depth
+  * 1st approach is easier to implement via recursion which is simpler.
+  * 
+  * Time: O(N) since all the nodes needs to be visited once, Space: O(N) since an additional encoded space of n
+  * is required.
+  * 
+  * @param root 
+  */
+
+/*
+ * Encodes a tree to a single string.
+ */
+function serialize(root: TreeNode | null): string {
+    const result: string[] = []
+    serializeHelper(root, result);
+    return result.join(";");
+};
+
+function serializeHelper(root: TreeNode | null, result: string[]) {
+    if (root === null) {
+        result.push("")
+        return
+    }
+    
+    result.push(root.val.toString())
+    serializeHelper(root.left, result)
+    serializeHelper(root.right, result)
+}
+
+function deserializeHelper(elements: string[]): TreeNode | null {
+    
+    const elem = elements.shift()
+    
+    if (elem === undefined || elem === "") return null;
+    
+    const node: TreeNode = {
+        val: parseInt(elem),
+        left: null,
+        right: null
+    };
+    
+    node.left = deserializeHelper(elements);
+    node.right = deserializeHelper(elements);
+    
+    return node;
+}
+
+/*
+ * Decodes your encoded data to tree.
+ */
+function deserialize(data: string): TreeNode | null {
+    const elements: string[] = data.split(";");
+    return deserializeHelper(elements);
+};
+
+
+/**
+ * Your functions will be called as such:
+ * deserialize(serialize(root));
+ */
diff --git a/level_medium/MinAdjacentSwapsForPalindrome.ts b/level_medium/MinAdjacentSwapsForPalindrome.ts
@@ -0,0 +1,96 @@
+class MinAdjacentSwapsForPalindrome {
+    countRecursive(input: string) {
+        return this.recursiveHelper(input.split(""), 0, input.length - 1);
+    }
+
+    // Case 1: Ends are equal, make 0 swaps and try for internal susbtring swaps.
+    // Case 2: Ends are not equal
+    // Step 1: Attempt to make ends equal using either multiple swaps in left or right. (Take Minimum)
+    // Step 2: Recursively try for substring.
+    // Return at base.
+    recursiveHelper(input: string[], beg: number, end: number) {
+
+        // Base condition, no swaps required.
+        if (end <= beg) return 0;
+
+        // Case 1: ends are equal.
+        if (input[beg] === input[end]) {
+            return this.recursiveHelper(input, beg + 1, end - 1);
+        }
+
+        // Case 2: ends are not equal.
+        const leftSwaps = this.swapLeft(input, beg, end);
+        
+        const rightSwaps = this.swapRight(input, beg, end);
+
+        if (leftSwaps < rightSwaps && leftSwaps !== Infinity) {
+            this.swap(input, beg, beg + leftSwaps);
+            return leftSwaps + this.recursiveHelper(input, beg + 1, end - 1);
+        } else if (rightSwaps !== Infinity) {
+            this.swap(input, end, end - rightSwaps);
+            return rightSwaps + this.recursiveHelper(input, beg + 1, end - 1);
+        } else {
+            return -1;
+        }
+    }
+
+    swap(input: string[], source: number, target: number) {
+        const temp = input[source]
+        input[source] = input[temp]
+        input[target] = temp;
+    }
+
+    swapLeft(input: string[], beg: number, end: number) {
+        let pivot = beg + 1;
+        while (pivot < end && input[end] !== input[pivot]) pivot++
+
+        if (pivot < end) return pivot - beg;
+        return Infinity;
+    }
+
+    swapRight(input: string[], beg: number, end: number) {
+        let pivot = end - 1;
+        while (pivot > beg && input[beg] !== input[pivot]) pivot--
+
+        if (pivot > beg) return end - pivot;
+        return Infinity
+    }
+
+    countIterative(input: string) {
+        let beg = 0, end = input.length - 1, swaps = 0;
+        const inputArr = input.split("")
+        while (end > beg) {
+            if (inputArr[end] === inputArr[beg]) {
+                // Case 1: Ends are equal, squeeze inwards.
+                end--; beg++;
+            } else {
+                // Case 2: Ends are not equal, displace left or right.
+                const leftSwaps = this.swapLeft(inputArr, beg, end)
+                const rightSwaps = this.swapRight(inputArr, beg, end)
+                if (leftSwaps < rightSwaps && leftSwaps !== Infinity) {
+                    this.swap(inputArr, beg, beg + leftSwaps)
+                    swaps += leftSwaps
+                } else if (rightSwaps !== Infinity) {
+                    this.swap(inputArr, end, end - rightSwaps)
+                    swaps += rightSwaps
+                } else {
+                    return -1
+                }
+                end--, beg++;
+            }
+        }
+
+        return swaps;
+    }
+}
+
+function testMinAdjacentSwapsPalindrome(input: string) {
+    const counter = new MinAdjacentSwapsForPalindrome();
+    console.log(`Min Adjacent Swaps for input recursive: ${input} is: ${counter.countRecursive(input)}`)
+    console.log(`Min Adjacent Swaps for input iterative: ${input} is: ${counter.countIterative(input)}`)
+}
+
+testMinAdjacentSwapsPalindrome("mamda")
+testMinAdjacentSwapsPalindrome("asflkj")
+testMinAdjacentSwapsPalindrome("aabb")
+testMinAdjacentSwapsPalindrome("ntiin")
