Day 63, #72， #75, Edit Distance， Sort Colors

Edit Distance
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
------------------------------------------------------------------------------------
Further reading:
Wagner–Fischer algorithm
Edit distance
http://www.youtube.com/watch?v=ocZMDMZwhCY

class Solution {
public:
    int minDistance(string word1, string word2) {
       int m = word1.length();
       int n = word2.length();
       
       vector<vector<int> > dp(m + 1,vector<int>(n + 1,0));
       
       // the distance of any first string to an empty second string
       for (int i = 0; i < m + 1; i++) {
           dp[i][0] = i;
       }
       
       // the distance of any second string to an empty first string
       for (int i = 0; i < n + 1; i++) {
           dp[0][i] = i;
       }
       
       for (int i = 1; i < m + 1; i++) {
           for (int j = 1; j < n + 1; j++) {
               if (word1[i - 1] == word2[j - 1]) {
                   dp[i][j] = dp[i - 1][j - 1]; 
               }else {
                   int temp = min(dp[i][j - 1],dp[i - 1][j]);
                   dp[i][j] = min(temp,dp[i - 1][j - 1]) + 1;
                   
               }
           }
       }
       return dp[m][n];
    }
};

Update on Nov-16-2014
if word[i] !=  word2[j] the cost from [i:end] to [j:end] is the minimal among

1. cost of insert + [i:end] [j - 1:end]
2. cost of delete + [i - 1:end] [j:end]
3. cost of replace + [i:end] [j:end]

if word1[i] == word2[j], then the distance of [i:end] and [j:end] is [i-1:end] and [j-1:end]
Improvement on this algorithm - Wagner–Fischer algorithm

O(n) space

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(),n = word2.length();
        if (m == 0) return n;
        if (n == 0) return m;
        vector<int> dp(n + 1,0);
        vector<int> pre(n + 1,0);
        for (int i = 0; i <= n; i++) {
            pre[i] = i;
        }
        
        for (int i = 1; i <= m; i++) {
            dp[0] = i;
            
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[j] = pre[j - 1];
                }else {
                    dp[j] = 1 + min(pre[j],min(dp[j - 1],pre[j - 1]));
                }
            }
            pre = dp;
        }
        
        return dp[n];
    }
};

递归：有重复子问题，所以用DP

int minDistance(string s1,string s2,int i,int j) {
    if (i == s1.length() && j == s2.length()) return 0;
    if (i == s1.length()) return s2.length() - j + 1;
    if (j == s2.length()) return s1.length() - i + 1;
    
    if (s1[i] == s2[j]) return edit(s1,s2,i + 1,j + 1);
    return 1 + min(edit(s1,s2,i + 1, j + 1),min(edit(s1,s2,i + 1,j),edit(s1,s2,i,j + 1)));
}

Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?---------------------------------------------------------
One pass

class Solution {
public:
    void sortColors(int A[], int n) {
        int itr = 0;
        int ptrZero = 0;
        int ptrTwo = n - 1;
        while (itr <= ptrTwo) {
            if (A[itr] == 1) {
                itr++;
            }else if (A[itr] == 0) {
                swap(A[itr],A[ptrZero]);
                ptrZero++;
                if (ptrZero >= itr) {
                    itr++;
                }
            }else if (A[itr] == 2) {
                swap(A[itr],A[ptrTwo]);
                ptrTwo--;
            }
        }
    }
};

Update on Jan-26-2015
re-factoried

class Solution {
public:
    void swap(int A[], int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    void sortColors(int A[], int n) {
        int start = 0;
        int end = n - 1;
        int itr = 0;
        
        while (itr <= end) {
            if (A[itr] == 0) {
                swap(A,itr,start);
                start++;
                itr++;
            }else if (A[itr] == 2) {
                swap(A,itr,end);
                end--;
            }else {
                itr++;
            }
        }
    }
};