There are bunch of different indices in the database world, you are probably most familiar with B-tree index. Different kind of index will have great impact on performance, bitmap index can be very helpful in some use case.

**Case**

Suppose Columbia university has a following table for the database course:

And suppose the course is so popular that millions of people take it, so the table is going to be huge.

Now we want to run the following SQL statement:

SELECT * FROM table WHERE Gender='male' AND Pass='false';

**No index on ‘Pass’ and ‘Gender’ column**

If we don’t use any index, the process will be scanning the whole table record by record million times and return the result set. But I’m sure we can do better than this.

If we don’t use any index, the process will be scanning the whole table record by record million times and return the result set. But I’m sure we can do better than this.

**B-tree index on ‘Pass’ and ‘Gender’ column**

So everyone knows index is going to help searching in database by sorting the entries. Is it going to faster if we put index on those columns we care about?

Not necessarily.

Index is not magic. If 50% of the records in table is ‘Gender=male’ and 50% of the records is ‘Pass=true’. Then the sql statement is going to return a very large dataset, maybe 30% of the whole data. In this case, the percentage of result set is considerable large compares to the original table, than the database optimizer will choose not to use the index even you have the index built.

Most probably, b-tree index is going to end up the same path as no index situation, scan the whole table record by record.

**B-tree index on ‘Pass’ and ‘Gender’ column**

So we know B-tree index is not going to help much on low cardinality situations. Here comes the use case of bitmap index.

We create one set of vectors for each of the column we care, in this case, ‘Gender’ and ‘Pass’. So now we have the 2 following set of vectors:

When we try to execute `SELECT * FROM table WHERE Gender='male' AND Pass='false';`

, it will do a vector AND operation:

Voila.

**When to use bitmap index**

- When the column you want to search on has low cardinality (gender, marriage status, etc).
- When the data in the column is kind of static, at least not updated frequently. This is because when we try to update a column with low cardinality, it might take a long time. During the lengthy time, the table is locked and the other user can’t do anything.

* *One thing to notice is MySQL is not supporting bitmap index for now (the only database that is supporting bitmap index I know about is Oracle database) , it’s in there work log for future feature though: https://dev.mysql.com/worklog/task/?id=1524*

In mysql, as well as other database system, there are many ways to get rid of data or table itself. So what are the differences?

**DML vs DDL**

In order to know the difference better, you have to know SQL commands are basically divided into:

- DML (Data Manipulation Language)
- DDL (Data Definition Language)
- DCL (Data Control Language)
- TCL(Transaction Control Language)

DML deal with data manipulation (CRUD), which is probably what everyone uses most commonly. DML usually needs to commit explicitly to take effect. DML statements include:

- SELECT: retrieve data from database
- INSERT: insert data into database
- UPDATE: update existing data in database
**DELETE: delete existing data in database**- LOCK TABLE: concurrency control for table in database

DDL deal with data definition – schema changes, build and modify the structure of tables and other objects. This means it deals with how data resides in the database. DDL statement has a implicit commit, which means it will take effect immediately. DDL statements include:

- CREATE: create database or objects including table, index, triggers, procedures, etc
**DROP: delete objects from database****TRUNCATE: delete all records from the table as well as the space allocated to the records**- ALTER: alter the structure of existing table or objects
- RENAME: rename an object

DCL deals with access control for database systems. DCL statements include:

- GRANT: grant user access privileges to database
- REVOKE: take the privileges back

TCL deals with transaction in database. TCL statements include:

- COMMIT: commit the current transaction
- ROLLBACK: rollback transaction in case of any exception or error
- SET TRANSACTION: specify attributes for transaction

**DELETE vs TRUNCATE**

In short, TRUNCATE is faster than DELETE.

- DELETE is meant for data manipulation, it deletes record row by row, hence requires a row level lock.
- DELETE keeps all the logs for deleting rows so that we can recover from the deletion in case anything happens. It supports rollback, which is the main reason it’s slower than truncate.
- DELETE will trigger the on delete triggers.
- DELETE won’t free space

As opposed:

- TRUNCATE is not meant for data manipulation, it remove all data in table, hence requires a table level lock.
- TRUNCATE does not keep logs for deleting rows. Hence, truncate is not available for rollback based on logs*.
- TRUNCATE won’t trigger on delete triggers
- TRUNCATE will free space, as well as re-render the auto increment indices.

** There is always exception :-D. If you use TRUNCATE command within a transaction, it can be rolled back.*

**TRUNCATE vs DROP**

DROP goes even further. It will removes the table from the database completely. This includes removing all data and associated objects, such as indexes and constraints. If you dropped a table, not only would you remove all the data, but the structure as well.

Similar with TRUNCATE, you can only row back if you execute DROP within a transaction.

]]>The problem description is as follow:

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */

In case you are not familiar with Binary Search Tree, go through wiki from the link. A intuitive way is to get the in-order traversal. The correct order of in-order traversal of BST should be ascending. If two elements are swapped in BST, it will be reflected through in-order traversal’s order.

**Naive Approach**

Edit Recover Binary Search Tree on GitHub

1. Get the in-order traversal list of BST 2. Traverse the list, find the two elements in wrong order 3. Swap the two elements in wrong order

public class Solution { public void recoverTree(TreeNode root) { List<TreeNode> list = new LinkedList<TreeNode>(); //get the inorder traveral list of tree builder(root, list); if(list.size()<2) { return; } TreeNode first = null; TreeNode second = null; //find two nodes with wrong order TreeNode pre = list.get(0); for(int i=1; i<list.size(); i++) { TreeNode cur = list.get(i); if(cur.val<pre.val) { if (first == null) { first = pre; } second = cur; } pre = cur; } //swap two nodes back swap(first,second); return; } private void swap(TreeNode first, TreeNode second) { if(first!=null && second!=null){ int temp = first.val; first.val = second.val; second.val = temp; } return; } private void builder(TreeNode root, List<TreeNode> result) { if (root==null){ return; } builder(root.left, result); result.add(root); builder(root.right, result); } }

Building the in-order traversal list take `O(n)`

time and `O(log n)`

space. Finding the two misplaced elements take `O(n)`

time and `O(n)`

space since we are saving the whole list. Thus this algorithm takes `O(n)`

time and space.

**Better Approach**

Edit Recover Binary Search Tree on GitHub

We can slightly improve the previous algorithm. Instead of saving the whole in-order traversal list, we could do the comparison when building the list.

public class Solution { TreeNode pre; TreeNode first; TreeNode second; private void inorder(TreeNode root){ if(root == null) return; inorder(root.left); if(pre == null){ pre = root; }else{ if(pre.val > root.val){ if(first == null){ first = pre; } second = root; } pre = root; } inorder(root.right); } private void swap(TreeNode first, TreeNode second) { if(first!=null && second!=null){ int temp = first.val; first.val = second.val; second.val = temp; } return; } public void recoverTree(TreeNode root) { pre = null; first = null; second = null; inorder(root); swap(first,second); } }

Building the in-order traversal list take `O(n)`

time and `O(log n)`

space. Two global variables saving the two misplaced elements take `O(1)`

space. Thus this algorithm takes `O(n)`

time and `O(log n)`

space.

**Morris Traversal Approach**

Edit Recover Binary Search Tree on GitHub

After previous effort, we know that solving the problem heavily rely on in-order tree traversal. Since we can solve in-order binary tree traversal with `O(n)`

time and `O(1)`

space, we could further improve the algorithm by doing the comparison through morris traversal. This algorithm takes `O(n)`

time and `O(1)`

space.

public class Solution { private void swap(TreeNode first, TreeNode second) { if(first!=null && second!=null){ int temp = first.val; first.val = second.val; second.val = temp; } return; } public void recoverTree(TreeNode root) { TreeNode cur = root; TreeNode pre = null; TreeNode parent = null; TreeNode first = null; TreeNode second = null; boolean found = false; while(cur != null) { if(cur.left == null) { if(parent!=null && parent.val > cur.val) { if(!found) { first = parent; found = true; } second = cur; } parent = cur; cur = cur.right; } else { pre = cur.left; while(pre.right!=null && pre.right!=cur) pre = pre.right; if(pre.right==null) { pre.right = cur; cur = cur.left; } else { pre.right = null; if(parent.val > cur.val) { if(!found) { first = parent; found = true; } second = cur; } parent = cur; cur = cur.right; } } } swap(first,second); } }]]>

Edit Reverse Nodes in k-Group on GitHub

The problem description is as follow:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed. For example, Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5

This problem seems difficult, but it will be much easier if we split the problem into small pieces.

**Reverse A Single Linked List**

Let’s take a look at the following singly linked list, we are trying to reverse nodes between `ListNode Pre`

to `ListNode End`

.

Since we are trying to reverse linked list between `ListNode Pre`

to `ListNode End`

, `ListNode Last = Pre.next`

will always be the last node of the reversed linked list.

public ListNode reverse(ListNode pre, ListNode end){ ListNode last=pre.next; ListNode cur=last.next; while (cur!=end){ last.next=cur.next; cur.next=pre.next; pre.next=cur; cur=last.next; } return last; }

The code above is trying to reverse linked list between `Pre`

and `Cur`

, and we could then reverse the whole linked list by moving `Cur`

to `Cur.next`

.

**Reverse Nodes in k-Group**

After previous analysis, this problem is simple. For a singly linked list, we create a Dummy ListNode and point to it’s head. Then we use previous algorithm to reverse nodes in k-group:

/** * Reverse a link list between pre and next exclusively * a linked list: * 0->1->2->3->4->5->6 * | | * pre next * after call pre = reverse(pre, next) * * 0->3->2->1->4->5->6 * | | * pre next */

public ListNode reverseKGroup(ListNode head, int k) { if (head ==null || k==1){ return head; } ListNode dummy =new ListNode (0); dummy.next=head; ListNode pre=dummy; ListNode cur=head; int i=0; while (cur!=null){ i++; if (i%k==0){ pre=reverse(pre,cur.next); cur=pre.next; } else { cur=cur.next; } } return dummy.next; }

Since we are traversing the singly linked list at most twice, the time complexity is `O(n)`

.

The problem description is as follow:

Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,3,2].

In case you are not familiar with inorder tree traversal, the following graph would help:

The in-order traversal for previous tree is `A, B, C, D, E, F, G, H, I`

.

**Recursive Approach**

Edit Binary Tree Inorder Traversal on GitHub

Recursive approach is pretty straight forward. The order of inorder is :

1. Left Child 2. Parent Node 3. Right Child

Thus the code will be:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result=new ArrayList<Integer> (); if (root==null){ return result; } builder(root, result); return result; } private void builder(TreeNode root, List<Integer> result){ if (root==null){ return; } builder(root.left, result); result.add(root.val); builder(root.right, result); } }

The time complexity of recursive approach is `O(n)`

since we are just traversing the whole tree once. The space complexity of recursive approach is `O(log n)`

.

**Iterative Approach**

Edit Binary Tree Inorder Traversal on GitHub

When it comes to iterative approach in tree traversal, always use a stack or queue. We could use a stack to imitate the recursive process we did above:

public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if(root == null) return res; Stack<TreeNode> stack = new Stack<TreeNode>(); //define a pointer to track nodes TreeNode p = root; while(!stack.empty() || p != null){ if(p != null){ stack.push(p); p = p.left; }else{ TreeNode t = stack.pop(); res.add(t.val); p = t.right; } } return res; } }

The time complexity of recursive approach is `O(n)`

since we are just traversing the whole tree once. The space complexity of recursive approach is `O(log n)`

.

**Morris Traversal Algorithm**

Edit Binary Tree Inorder Traversal on GitHub

Actually there’s a better way to solve the problem. Instead of using `O(log n)`

space, we could solve it with `O(l)`

space.

In order to solve the problem with `O(l)`

space, the most important question is **how to traverse back to parent node from child node**. Morris traversal introduce threaded binary tree. In threaded binary tree, we don’t have to assign additional space to every node pointing to the predecessor and successor, nor do we have to save the nodes into stack.

1. If left child of current node is empty, output current node. Set current's right child as current node 2. If left child of current node is not empty, find the in-order traversal predecessor node in its left subtree - If predecessor's right child is empty, predecessor's right child = current node. Current node = current node's left child. - If predecessor's right child is current node, set predecessor's right child back to empty (recover structure of tree). Output current node. Set current node = current node's right child. - There won't be other possibility according to definition of predecessor. Repeat process 1 and 2 until current node is empty.

The following graph would help a lot:

Here comes the code:

public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); TreeNode cur = root; TreeNode pre = null; while(cur != null) { if(cur.left == null) { res.add(cur.val); cur = cur.right; } else { pre = cur.left; while(pre.right!=null && pre.right!=cur) pre = pre.right; if(pre.right==null) { pre.right = cur; cur = cur.left; } else { pre.right = null; res.add(cur.val); cur = cur.right; } } } return res; } }

Since we are traversing each node at most twice, the time complexity is still `O(n)`

and we are only using `O(1)`

extra space.

]]>

The problem description is as follow:

Given a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,2,3].

In case you are not familiar with preorder tree traversal, the following graph would help:

The preorder traversal for previous tree is `F, B, A, D, C, E, G, I, H`

.

**Recursive Approach**

Edit Binary Tree Preorder Traversal on GitHub

Recursive approach is pretty straight forward. The order of preorder is :

1. Parent Node 2. Left Child 3. Right Child

Thus the code will be:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result=new ArrayList<Integer> (); if (root==null){ return result; } builder(root, result); return result; } private void builder(TreeNode root, List<Integer> result){ if (root==null){ return; } result.add(root.val); builder(root.left, result); builder(root.right, result); } }

The time complexity of recursive approach is `O(n)`

since we are just traversing the whole tree once. The space complexity of recursive approach is `O(log n)`

.

**Iterative Approach**

Edit Binary Tree Preorder Traversal on GitHub

When it comes to iterative approach in tree traversal, always use a stack or queue. We could use a stack to imitate the recursive process we did above:

public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if(root == null) return res; LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); TreeNode q = root; while(q!=null || !stack.isEmpty()) { if(q!=null) { stack.push(q); res.add(q.val); q = q.left; } else { q = stack.pop(); q = q.right; } } return res; } }

`O(n)`

since we are just traversing the whole tree once. The space complexity of recursive approach is `O(log n)`

.

**Morris Traversal Algorithm**

Edit Binary Tree Preorder Traversal on GitHub

Actually there’s a better way to solve the problem. Instead of using `O(log n)`

space, we could solve it with `O(l)`

space.

In order to solve the problem with `O(l)`

space, the most important question is **how to traverse back to parent node from child node**. Morris traversal introduce threaded binary tree. In threaded binary tree, we don’t have to assign additional space to every node pointing to the predecessor and successor, nor do we have to save the nodes into stack.

1. If left child of current node is empty, output current node. Set current's right child as current node 2. If left child of current node is not empty, find the in-order traversal predecessor node in its left subtree - If predecessor's right child is empty, set predecessor's right child = current node. Output current node. Set current node = current node's left child. - If predecessor's right child is current node, set predecessor's right child back to empty (recover structure of tree). Set current node = current node's right child. - There won't be other possibility according to definition of predecessor. Repeat process 1 and 2 until current node is empty.

The following graph would help a lot:

Here comes the code:

public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); TreeNode cur = root; TreeNode pre = null; while(cur != null) { if(cur.left == null) { res.add(cur.val); cur = cur.right; } else { pre = cur.left; while(pre.right!=null && pre.right!=cur) pre = pre.right; if(pre.right==null) { res.add(cur.val); pre.right = cur; cur = cur.left; } else { pre.right = null; cur = cur.right; } } } return res; } }

Since we are traversing each node at most twice, the time complexity is still `O(n)`

and we are only using `O(1)`

extra space.

]]>

The problem description is as follow:

Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [3,2,1].

In case you are not familiar with postorder tree traversal, the following graph would help:

The postorder traversal for previous tree is `A, C, E, D, B, H, I, G, F`

.

**Recursive Approach**

Edit Binary Tree Postorder Traversal on GitHub

Recursive approach is pretty straight forward. The order of postorder is :

1. Left Child 2. Right Child 3. Parent Node

Thus the code will be:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result=new ArrayList<Integer> (); if (root==null){ return result; } builder(root, result); return result; } private void builder(TreeNode root, List<Integer> result){ if (root==null){ return; } builder(root.left, result); builder(root.right, result); result.add(root.val); } }

`O(n)`

since we are just traversing the whole tree once. The space complexity of recursive approach is `O(log n)`

.

**Iterative Approach**

Edit Binary Tree Postorder Traversal on GitHub

When it comes to iterative approach in tree traversal, always use a stack or queue. We could use a stack to imitate the recursive process we did above:

public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if(root == null) { return res; } LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); TreeNode pre = null; TreeNode p =root; while(p != null || !stack.isEmpty()) { if(p!=null) { stack.push(p); p = p.left; } else { TreeNode peekNode = stack.peek(); if(peekNode.right!=null && pre != peekNode.right) { p = peekNode.right; } else { stack.pop(); res.add(peekNode.val); pre = peekNode; } } } return res; } }

`O(n)`

since we are just traversing the whole tree once. The space complexity of recursive approach is `O(log n)`

.

**Morris Traversal Algorithm**

Edit Binary Tree Postorder Traversal on GitHub

Actually there’s a better way to solve the problem. Instead of using `O(log n)`

space, we could solve it with `O(l)`

space.

In order to solve the problem with `O(l)`

space, the most important question is **how to traverse back to parent node from child node**. Morris traversal introduce threaded binary tree. In threaded binary tree, we don’t have to assign additional space to every node pointing to the predecessor and successor, nor do we have to save the nodes into stack.

Set current node as temporary node, name dump 1. If left child of current node is empty, set current node = current node's right child 2. If left child of current node is not empty, find the in-order traversal predecessor node in its left subtree - If predecessor's right child is empty, set predecessor's right child = current node. Set current node = current node's left child. - If predecessor's right child is current node, set predecessor's right child back to empty (recover structure of tree). Reversely output nodes from current node's left child to current node's predecessor (in other words, from current node's predecessor to current node's left child). Set current node = current node's right child. - There won't be other possibility according to definition of predecessor. Repeat process 1 and 2 until current node is empty.

The following graph would help a lot:

Here comes the code:

public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); TreeNode dummy = new TreeNode(-1); dummy.left = root; TreeNode cur = dummy; TreeNode pre = null; while(cur!=null) { if (cur.left==null) { cur = cur.right; } else { pre = cur.left; while (pre.right!=null && pre.right!=cur) pre = pre.right; if (pre.right==null) { pre.right = cur; cur = cur.left; } //Reversely output nodes from current node's left child //to current node's predecessor else { reverse(cur.left, pre); TreeNode temp = pre; while (temp != cur.left) { res.add(temp.val); temp = temp.right; } res.add(temp.val); reverse(pre, cur.left); pre.right = null; cur = cur.right; } } } return res; } private void reverse(TreeNode start, TreeNode end) { if (start == end) return; TreeNode pre = start; TreeNode cur = start.right; TreeNode next; while (pre != end) { next = cur.right; cur.right = pre; pre = cur; cur = next; } } }

Since we are traversing each node at most 3 times, the time complexity is still `O(n)`

and we are only using `O(1)`

extra space.

**Leetcode 206 Reverse Linked List**

The problem description is as follow:

Reverse a singly linked list: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */

This problem is basic, thus we should try to solve it in various ways. I tried iteratively and recursively.

**Iterative Approach**

Edit Reverse Linked List on GitHub

public class Solution { public ListNode reverseList(ListNode head) { if(head==null || head.next == null) return head; ListNode p1 = head; ListNode p2 = head.next; head.next = null; while(p1!= null && p2!= null){ ListNode temp = p2.next; p2.next = p1; p1 = p2; p2 = temp; } return p1; } }

The time complexity is `O(n)`

, we simply traverse the while linked list.

**Recursive Approach**

Edit Reverse Linked List on GitHub

public class Solution { public ListNode reverseList(ListNode head) { if(head==null || head.next == null) return head; //get second node ListNode second = head.next; //set first's next to be null head.next = null; ListNode rest = reverseList(second); second.next = head; return rest; } }

**Leetcode 92 Reverse Linked List II**

Edit Reverse Linked List II on GitHub

The problem description is as follow:

Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: The definition of linked list is same as previous problem. Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

This problem is mostly the same as previous. The only thing we have to keep aware is to do it in-place and in one-pass. We just have to:

1. Traverse to the reverse starting point 2. Do the in-place reverse exactly the same as previous, iteratively or recursively as you like 3. While doing reverse, keep track of the reverse starting point and ending point so we can link the reversed part of list to the rest part

public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode helper = new ListNode(0); helper.next = head; ListNode p = helper; for(int i = 1; i < m; i++) p = p.next; p.next = reverse(p.next, n - m + 1); return helper.next; } private ListNode reverse(ListNode head, int n){ ListNode node = head, prev = null, next = null; for(int i = 0; i < n; i++){ next = node.next; node.next = prev; prev = node; node = next; } head.next = node; return prev; } }]]>

The problem description is as follow:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character

This is a classical DP problem. I use a 2-D matrix `dp[][]`

to save all the data. `dp[i][j]`

stands for the edit distance between two strings with length *i* and *j*, `word1[0,...,i-1]`

and `word2[0,...,j-1]`

.

Now we only have to figure how to get the recursive formula for `dp[i][j]`

from historical data we already got, which is equivalent to getting the relationship between `dp[i][j]`

and `dp[i-1][j-1]`

. Let’s say we transform from `string word1`

to `string word2`

. The first string has length *i* and it’s last character is `word1.charAt(i) = x`

; the second string has length *j *and its last character is `word2.charAt(j) = y`

.

1. if x == y, then dp[i][j] == dp[i-1][j-1] 2. if x != y, and we insert y for word1, then dp[i][j] = dp[i][j-1] + 1 3. if x != y, and we delete x for word1, then dp[i][j] = dp[i-1][j] + 1 4. if x != y, and we replace x with y for word1, then dp[i][j] = dp[i-1][j-1] + 1 When x!=y, dp[i][j] is the min of the three situations.

And we have the initial condition as `dp[i][0] = i, dp[0][j] = j`

Here comes the code:

public class Solution { public int minDistance(String word1, String word2) { int L1 = word1.length(); int L2 = word2.length(); // L1+1, L2+1, because finally return dp[L1][L2] int[][] dp = new int[L1 + 1][L2 + 1]; for (int i = 0; i <= L1; i++) { dp[i][0] = i; } for (int j = 0; j <= L2; j++) { dp[0][j] = j; } //iterate though, and check last char for (int i = 0; i < L1; i++) { char c1 = word1.charAt(i); for (int j = 0; j < L2; j++) { char c2 = word2.charAt(j); //if last two chars equal if (c1 == c2) { //update dp value for +1 length dp[i + 1][j + 1] = dp[i][j]; } else { int replace = dp[i][j] + 1; int insert = dp[i][j + 1] + 1; int delete = dp[i + 1][j] + 1; int min = replace > insert ? insert : replace; min = delete > min ? min : delete; dp[i + 1][j + 1] = min; } } } return dp[L1][L2]; } }]]>

The problem description is as follow:

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great": great / \ gr eat / \ / \ g r e at / \ a t To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat". rgeat / \ rg eat / \ / \ r g e at / \ a t We say that "rgeat" is a scrambled string of "great". Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae". rgtae / \ rg tae / \ / \ r g ta e / \ t a We say that "rgtae" is a scrambled string of "great". Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

**Recursive Approach**

Edit Scramble String on GitHub

The recursive approach is straight-forward. If `string s1`

is a scrambled string of `string s2`

, then there must exists a point that breaks `string s1`

into two parts `s11`

and `s12`

and a point that breaks `string s2`

into two parts `s21`

and `s22`

where:

1. s11 is a scrambled string of s21, s12 is a scrambled string of s22. Or 2. s12 is a scrambled string of s21, s11 is a scrambled string of s22.

In order to make the recursive method more efficient, we can add some simple validation. If `string s1`

is a scrambled string of `string s2`

, then they must share the same characters and have same length.

public class Solution { public boolean isScramble(String s1, String s2) { //Check lengths. if (s1.length() != s2.length()) return false; if (s1.equals(s2)) return true; int L = s1.length(); //Check characters. int[] chars = new int[26]; for (int i = 0; i < L; i++) { chars[s1.charAt(i) - 'a']++; chars[s2.charAt(i) - 'a']--; } for (int i = 0; i < 26; i++) { if (chars[i] != 0) return false; } //More letters for (int i = 1; i < L; i++) { String s11 = s1.substring(0, i); String s12 = s1.substring(i, L); String s21 = s2.substring(0, i); String s22 = s2.substring(i, L); if (isScramble(s11, s21) && isScramble(s12, s22)) return true; s21 = s2.substring(0, L - i); s22 = s2.substring(L - i, L); if (isScramble(s11, s22) && isScramble(s12, s21)) return true; } return false; } }

**Dynamice Programming Approach**

Edit Scramble String on GitHub

Even if we add bunch of validations in the recursive approach, the time complexity is still not polynomial. In this case, we should seek a more efficient approach – DP approach.

I use a 3-D matrix `scramble[][][]`

to save all the states. Say `scramble[i][j][k]`

, `i`

stands for the starting index of `string s1`

and `j`

stands for the starting index of `string s2`

. `k`

stands for the length of current string. `scramble[i][j][k] = true`

means `s1.substring(i,i+k)`

and `s1.substring(j,j+k)`

are scrambled strings.

Now we only have to figure how to get the recursive formula for `scramble[i][j][k]`

from historical states we already got. As we discussed in the recursive approach, if `string s1`

is a scrambled string of `string s2`

, then there must exists a point that breaks `string s1`

into two parts `s11`

and `s12`

and a point that breaks `string s2`

into two parts `s21`

and `s22`

where:

1. s11 is a scrambled string of s21, s12 is a scrambled string of s22. Or 2. s12 is a scrambled string of s21, s11 is a scrambled string of s22.

Translating words into maths, we got:

For 1<=k<len, scramble[i][j][len] |= (scramble[i][j][k]&&scramble[i+k][j+k][len-k] || scramble[i][j+len-k][k]&&scramble[i+k][j][len-k])

Here comes the code:

public class Solution { public boolean isScramble(String s1, String s2) { //Check lengths. if (s1==null || s2==null || s1.length() != s2.length()) return false; if (s1.equals(s2)) return true; int L = s1.length(); // scramble[i][j][k]=true means: s1.substring(i,i+k) and s2.substring(j,j+k) is scramble // Thus scramble[i][j][0] has no meaning, k start from 1 boolean[][][] scramble = new boolean[L][L][L+1]; // Initiate scramble[][][], note that in Java boolean's default value is false for (int i = 0; i < L; i++) { for (int j = 0; j < L; j++) if (s1.charAt(i) == s2.charAt(j)) scramble[i][j][1] = true; } for (int len = 2; len <= L; len++) { for (int i = 0;i < L - len + 1; i++) { for(int j = 0; j < L - len + 1; j++) { for(int k = 1; k < len; k++) { scramble[i][j][len] |= (scramble[i][j][k]&&scramble[i+k][j+k][len-k] || scramble[i][j+len-k][k]&&scramble[i+k][j][len-k]); } } } } return scramble[0][0][L]; } }

The time complexity is `O(n^4)`

and space complexity is `O(n^3)`

, all polynomial.

Now we are happy

]]>