LC: 1055. Shortest Way to Form String - spiralgo/algorithms GitHub Wiki

The Essence:

This question is a fairly simple two pointers problem.

The target is composed of substrings that are subsequences of the source string. From this, the problem-solver can infer the solution that we should compare characters of the target and the source in some way. We can do this by looping through the source string each time and checking if the given char at p1 is the same as the one in the target at p2.

Details:

The procedure should keep track of p2 somewhere until it fully traverses the target string. If so, how many times the source is looped through should be returned, which corresponds to how many subsequences of the source has been checked.

While iterating through the source string, if p2 does not move anywhere, that means that target contains a char at p2 that p1 does not contains, which means that target cannot be constructed from the source string. We can check this with a simple variable.

The procedure described above looks like this: Strings