leetcode Question 106: Substring with Concatenation of All Words

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Analysis:

Try to think this problem straightforward:
Say in L there are m strings with length n. 
What string is required to match in S?     A length of m*n string start with each position in S.
What is a match?  In the m*n long string, every string in L appear only once.

So the algorithm is:
Scan every m*n long string start from each position in S, see if all the strings in L have been appeared only once using Map data structure. If so, store the starting position.

Yes, do not consider any DP or DFS solutions, just using the hash map and loop.

Code(C++):

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;
        int num = L.size();
        int len = L[0].size();
        if (num==0){return res;}
        map<string,int> mp;  
        for (int i=0;i<num;i++){mp[L[i]]++;}      
         
        int i=0;
        while ((i+num*len-1)<S.size()){
            map<string,int> mp2;
            int j=0;
            while (j<num){
                string subs = S.substr(i+j*len,len);
                if (mp.find(subs)==mp.end()){
                        break;
                }else{
                    mp2[subs]++;
                    if (mp2[subs]>mp[subs]){
                        break;
                    }
                    j++;  
                }
            }
            if (j==num){res.push_back(i);}
            i++;
        }
     
        return res;
    }
};

Code(Python):

class Solution:
    # @param S, a string
    # @param L, a list of string
    # @return a list of integer
    def findSubstring(self, S, L):
        res = []            # result list
        num = len(L)        # length of the str list 
        ls = len(S)
        if num == 0:
            return []
        str_len = len(L[0]) # length of each str
        #create the map: count the occurrance of each string
        #Note that set(L) is used to reduce the time, otherwise will not pass the large test
        map_str = dict((x,L.count(x)) for x in set(L))
        i = 0
        while i + num * str_len - 1 < ls:
            map_str2 = {}
            j = 0
            while j < num:
                subs = S[i + j * str_len:i + j * str_len + str_len ]
                if not subs in map_str:
                    break
                else:
                    # Note that dict.get(key, default_val) is used to handel the case that key NOT exist
                    map_str2[subs] = map_str2.get(subs, 0) + 1
                    if map_str2[subs]>map_str[subs]:
                        break
                    j = j + 1
            if j == num:
                res.append(i)
            i = i + 1
        
        return res

        

leetcode Question 29: Edit Distance

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

Analysis:
At the first glance, we might think this is a DFS problem, but if we see it is hard to find a quick DFS thought and the problem requires some optimal result (here is the minimum), DP is a good direction to consider.
Actually this is a classic DP problem:
The state is:   table[i][j]=minimum number steps convert word1[1:i] to word2[1:j] (here assume string starts from 1).

The optimal function is:  table[i+1][j+1] = min [table[i][j]+1 or 0 (+0 if word1[i+1]==word2[j+1], else +1),   table[i][j+1]+1, table[i+1][j]+1 ].

Initialization:
table[0][i] = i  i=1:|word1|          here 0 means "", any string convert to "" needs the length of string
table[j][0] = j  i=1:|word2|
table[0][0]=0    "" convert to  "" need 0 steps.



Code(updated 201401):

class Solution {
public:
    int minDistance(string word1, string word2) {
        int s1 = word1.size();
        int s2 = word2.size();
        if (s1==0){return s2;}
        if (s2==0){return s1;}
        vector<vector<int> > w(s1+1,vector<int>(s2+1,0));
        for (int i=0;i<=s1;i++){w[i][0]=i;}
        for (int i=0;i<=s2;i++){w[0][i]=i;}
        
        for (int i=1;i<=s1;i++){
            for (int j=1;j<=s2;j++){
                w[i][j]=min(w[i-1][j]+1,w[i][j-1]+1);
                if (word1[i-1]==word2[j-1]){
                    w[i][j]=min(w[i-1][j-1],w[i][j]);
                }else{
                    w[i][j]=min(w[i-1][j-1]+1,w[i][j]);
                }
            }
        }
        return w[s1][s2];
    }
};

Code:

class Solution {
public:
    int minDistance(string word1, string word2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len1 = word1.size();
        int len2 = word2.size();
        
        vector<vector<int> > table(len1+1,vector<int>(len2+1,0));
        
        for (int i=1;i<=len1;i++){
            table[i][0]=i;
        }
        
        for (int i=1;i<=len2;i++){
            table[0][i]=i;
        }
        
        for(int i=0;i<len1;i++){
            for (int j=0;j<len2;j++){                         
                table[i+1][j+1]=min(table[i+1][j],table[i][j+1])+1;
                if (word1[i]==word2[j]){
                    table[i+1][j+1]=min(table[i+1][j+1],table[i][j]);
                }else{
                    table[i+1][j+1]=min(table[i+1][j+1],table[i][j]+1);
                }
            }
        }
        
        return table[len1][len2];
    }
};