“This is the 14th day of my participation in the First Challenge 2022.

Today is New Year’s Eve, everyone happy New Year ha ~ year of the tiger universiade ~~

Algorithm continues, this is a very typical problem: “judge subsequence”, using the double pointer solution ~

Rush is done ~

Topic:

Given the strings s and t, determine whether S is a subsequence of t.

A subsequence of strings is a new string formed by deleting some (or none) characters from the original string without changing the relative positions of the remaining characters. (For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not).

Advanced:

If S has a lot of inputs, it’s called S1, S2… Sk where k >= 1 billion, you need to check in order to see if they are subsequences of T. How would you change the code in this case?

Example 1: Input: s = "ABC ", t =" AHBGDC "Output: true Example 2: Input: s =" axC ", t = "AHBGDC" Output: falseCopy the code
  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • Both strings consist of lowercase characters only.

Answer:

The question is, is s a subsequence of T, so if you can find any way that S can appear in T, you can say that s is a subsequence of T. When we match from front to back, we see that it is optimal to greedily match the first character each time.

Given that character C is currently required to match, and the position of character C in t is x1 and x2 (x1 < x2), then the optimal solution is to be greedy for x1, because any character after x2 is also available to x1, and there is a better chance that the match will be successful through the optional characters between x1 and X2.

Thus, we initialize two Pointers, I and j, to the initial positions of S and t, respectively. Each greedy match, I and j move to the right at the same time on success, match the next position of S, j moves to the right on failure, I stays the same, try to match s with the next character of T. And finally if I moves to the end of S, then S is a subsequence of T.

JavaScript implementation:

// isSubSequence O(N), Space complexity O(1) func isSubSequence(s, T string) bool {m, n := len(s), len(t) I, j := 0, 0 for i < m && j < n { if s[i] == t[j] { i++ } j++ } return i == m }Copy the code

The above –

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~