Leetcode 1055: Shortest Way to Form String

Constraints:

• Both the source and target strings consist of only lowercase English letters from "a"-"z".
• The lengths of source and target string are between 1 and 1000.

Notes:

The algorithm to this question is pretty straightforward: greedy. Scan target from left: as along as it is a sub-sequence of source, continue the scan. When it reaches the end of source, it means that we have to adopt another subsequence of source to form the rest part of target. so we simply update the count by adding 1, and continue the above process until finishing the scan.

This question can be view as a follow up to question Leetcode 392 and Leetode 792

See the code below:

class Solution {
public:
    int shortestWay(string source, string target) {
        int res = 0;
        vector<vector<int>> ids(26);//used to record the ids of each letter in source
        for(int i=0; i<source.size(); ++i) {
            ids[source[i]-'a'].push_back(i);
        }
        int idx = -1;
        bool cannot = false;
        for(int i=0; i<target.size(); ++i) {
            int j = target[i] - 'a';
            if(ids[j].empty()) {
                cannot = true;
                break;
            }
            auto it = upper_bound(ids[j].begin(), ids[j].end(), idx);//the first bigger than idx
            if(it == ids[j].end()) {
                ++res;
                idx = -1;
                --i;//target[i] is not matched yet
                continue;
            }
            idx = *it;
            if(idx+1==source.size()) {
                ++res;
                idx = -1;
            }
        }
        if(idx != -1) ++res; //the last remaining part of source
        return (cannot || !res) ? -1 : res;
    }
};

The code can be modified as:

class Solution {
public:
    int shortestWay(string source, string target) {
        int res = 0;
        vector<vector<int>> ids(26);//used to record the ids of each letter in source
        for(int i=0; i<source.size(); ++i) {
            ids[source[i]-'a'].push_back(i);
        }
        int idx = -1;
        bool cannot = false;
        for(int i=0; i<target.size(); ++i) {
            int j = target[i] - 'a';
            if(ids[j].empty()) {
                cannot = true;
                break;
            }
            auto it = upper_bound(ids[j].begin(), ids[j].end(), idx);//the first bigger than idx
            if(it != ids[j].end()) idx = *it;
            if(it == ids[j].end() || idx+1==source.size()) {
                if(it == ids[j].end()) --i;//target[i] is not matched yet
                ++res;
                idx = -1;
            }
        }
        if(idx != -1) ++res; //the last remaining part of source
        return (cannot || !res) ? -1 : res;
    }
};