单词连接算法

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).

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

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

public int minDistance(String word1, String word2) {
    int m=word1.length();
    int n=word2.length();
    if(word1.equals(word2)){
        return 0;
    }
    if(m==0||n==0){
        return Math.abs(m-n);
    }
    int[][] ds = new int[m+1][n+1];
    for(int i=0; i<=m; i++){
        ds[i][0] = i;
    }
    for(int j=0; j<=n; j++){
        ds[0][j] = j;
    }
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(word1.charAt(i-1)==word2.charAt(j-1)){
                ds[i][j] = ds[i-1][j-1];
            }else{
                ds[i][j] = Math.min(ds[i][j-1],Math.min(ds[i-1][j-1],ds[i-1][j]))+1;
            }
        }
    }
    return ds[m][n];
}