Fuck LeetCode  >  Dynamic Programming  >  392. Is Subsequence  >  Solved in Python, C++, Java, C#, Go, JavaScript, Ruby  >  Contribute or Repost

    LeetCode link: 392. Is Subsequence, difficulty: Medium.

    Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

    A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

    Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 10^9, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

    Example 1:

    Input: s = "abc", t = "ahbgdc"

    Output: true

    Example 2:

    Input: s = "axc", t = "ahbgdc"

    Output: false

    Constraints:

    • 0 <= s.length <= 100
    • 0 <= t.length <= 10^4
    • s and t consist only of lowercase English letters.

    Intuition
    PreviousNext

    • Define two pointers, initially pointing to the heads of two strings respectively, and reference characters with t[i] and s[j].
    • During the traversal of t, i is automatically incremented by 1, and if t[i] == s[j], then j += 1.
    • If j >= s.length, return true. If t is traversed and still not returned in advance, return false.

    Complexity

    Time complexity

    O(N)

    Space complexity

    O(1)

    Solution in languages: Python C++ Java C# Go JavaScript Ruby

    Python # 

    class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if s == "":
            return True

        s_index = 0

        for i in range(len(t)):
            if t[i] == s[s_index]:
                s_index += 1

                if s_index >= len(s):
                    return True

        return False

    C++ # 

    class Solution {
public:
    bool isSubsequence(string s, string t) {
        if (s.empty()) {
            return true;
        }

        int s_index = 0;

        for (int i = 0; i < t.length(); i++) {
            if (t[i] == s[s_index]) {
                s_index++;

                if (s_index >= s.length()) {
                    return true;
                }
            }
        }

        return false;
    }
};

    Java # 

    class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.isEmpty()) {
            return true;
        }

        int sIndex = 0;

        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) == s.charAt(sIndex)) {
                sIndex++;

                if (sIndex >= s.length()) {
                    return true;
                }
            }
        }

        return false;
    }
}

    C# # 

    public class Solution
{
    public bool IsSubsequence(string s, string t)
    {
        if (string.IsNullOrEmpty(s))
        {
            return true;
        }

        int sIndex = 0;

        for (int i = 0; i < t.Length; i++)
        {
            if (t[i] == s[sIndex])
            {
                sIndex++;

                if (sIndex >= s.Length)
                {
                    return true;
                }
            }
        }

        return false;
    }
}

    Go # 

    func isSubsequence(s string, t string) bool {
    if len(s) == 0 {
        return true
    }

    sIndex := 0

    for i := 0; i < len(t); i++ {
        if t[i] == s[sIndex] {
            sIndex++

            if sIndex >= len(s) {
                return true
            }
        }
    }

    return false
}

    JavaScript # 

    /**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    if (s.length === 0) {
        return true;
    }

    let sIndex = 0;

    for (let i = 0; i < t.length; i++) {
        if (t[i] === s[sIndex]) {
            sIndex++;

            if (sIndex >= s.length) {
                return true;
            }
        }
    }

    return false;
};

    Ruby # 

    # @param {String} s
# @param {String} t
# @return {Boolean}
def is_subsequence(s, t)
  return true if s.empty?

  s_index = 0

  t.each_char.with_index do |char, i|
    if char == s[s_index]
      s_index += 1
      return true if s_index >= s.length
    end
  end

  false
end
    Solution in languages: Python C++ Java C# Go JavaScript Ruby

    Other languages

    Welcome to contribute code to our GitHub repository, thanks! The location of this solution is 392. Is Subsequence.

    Intuition of solution 2: Dynamic Programming (Two-Dimensional)

    • Solution 1 is essentially a "dynamic programming" algorithm implemented with rolling variables. It is easy to understand, and the space complexity is reduced to O(1).
    • But now, not only do we not reduce the dimension, but we also increase the dimension. It will be more difficult to understand and implement. So why do this thankless task?
      Click to view the answer

      Because it can handle a more complex scenario (e.g. 583. Delete Operation for Two Strings) that is common in dynamic programming.

    • In this question, can we use a one-dimensional rolling array to implement the "dynamic programming" algorithm?
      Click to view the answer

      Of course, but considering that a one-dimensional rolling array is not as easy to understand as a two-dimensional array, and the implementation process is also prone to errors, so here I didn't give the relevant code implementation. If you are interested, you can try it.

    Pattern of "Dynamic Programming"

    "Dynamic programming" is divided into five steps

    1. Determine the meaning of each value of the array dp.
    2. Initialize the value of the array dp.
    3. Fill in the dp grid data "in order" according to an example.
    4. Based on the dp grid data, derive the "recursive formula".
    5. Write a program and print the dp array. If it is not as expected, adjust it.

    Detailed description of these five steps

    1. Determine the meaning of each value of the array dp.
      • First determine whether dp is a one-dimensional array or a two-dimensional array. A one-dimensional rolling array means that the values ​​of the array are overwritten at each iteration. Most of the time, using one-dimensional rolling array instead of two-dimensional array can simplify the code; but for some problems, such as operating "two swappable arrays", for the sake of ease of understanding, it is better to use two-dimensional array.
      • Try to use the meaning of the return value required by the problem as the meaning of dp[i] (one-dimensional) or dp[i][j] (two-dimensional). It works about 60% of the time. If it doesn't work, try other meanings.
      • Try to save more information in the design. Repeated information only needs to be saved once in a dp[i].
      • Use simplified meanings. If the problem can be solved with boolean value, don't use numeric value.
    2. Initialize the value of the array dp. The value of dp involves two levels:
      1. The length of dp. Usually: condition array length plus 1 or condition array length.
      2. The value of dp[i] or dp[i][j]. dp[0] or dp[0][0] sometimes requires special treatment.
    3. Fill in the dp grid data "in order" according to an example.
      • The "recursive formula" is the core of the "dynamic programming" algorithm. But the "recursive formula" is obscure. If you want to get it, you need to make a table and use data to inspire yourself.
      • If the original example is not good enough, you need to redesign one yourself.
      • According to the example, fill in the dp grid data "in order", which is very important because it determines the traversal order of the code.
      • Most of the time, from left to right, from top to bottom. But sometimes it is necessary to traverse from right to left, from bottom to top, from the middle to the right (or left), such as the "palindrome" problems. Sometimes, it is necessary to traverse a line twice, first forward and then backward.
      • When the order is determined correctly, the starting point is determined. Starting from the starting point, fill in the dp grid data "in order". This order is also the order in which the program processes.
      • In this process, you will get inspiration to write a "recursive formula". If you can already derive the formula, you do not need to complete the grid.
    4. Based on the dp grid data, derive the "recursive formula".
      • There are three special positions to pay attention to: dp[i - 1][j - 1], dp[i - 1][j] and dp[i][j - 1], the current dp[i][j] often depends on them.
      • When operating "two swappable arrays", due to symmetry, we may need to use dp[i - 1][j] and dp[i][j - 1] at the same time.
    5. Write a program and print the dp array. If it is not as expected, adjust it.
      • Focus on analyzing those values that are not as expected.

    After reading the above, do you feel that "dynamic programming" is not that difficult? Try to solve this problem. 🤗

    Steps

    It is a question of comparing two strings. After doing similar questions many times, we will develop an intuition to use dynamic programming with two-dimensional arrays.

    Common steps in dynamic programming

    These five steps are a pattern for solving dynamic programming problems.

    1. Determine the meaning of the dp[i][j]
      • Since there are two strings, we can use two-dimensional arrays as the default option.
      • At first, try to use the problem's return value as the value of dp[i][j] to determine the meaning of dp[i][j]. If it doesn't work, try another way.
      • dp[i][j] represents whether the first i letters of s are a subsequence of t's first j letters.
      • dp[i][j] is true or false.

    2. Determine the dp array's initial value

      • Use an example:

        After initialization, the 'dp' array would be:
s = "abc", t = "ahbgdc"
#     a h b g d c
#   T T T T T T T # dp[0]
# a F F F F F F F
# b F F F F F F F
# c F F F F F F F

      • dp[0][j] = true because dp[0] represents the empty string, and empty string is a subsequence of any string.

      • dp[i][j] = false (i != 0).

    3. Determine the dp array's recurrence formula

      • Try to complete the dp grid. In the process, you will get inspiration to derive the formula.

        1. s = "a", t = "ahbgdc" 
#     a h b g d c
#   T T T T T T T
# a F T T T T T T # dp[1]

        2. s = "ab", t = "ahbgdc" 
#     a h b g d c
#   T T T T T T T
# a F T T T T T T
# b F F F T T T T

        3. s = "abc", t = "ahbgdc"
#     a h b g d c
#   T T T T T T T
# a F T T T T T T
# b F F F T T T T
# c F F F F F F T # dp[3]

      • When analyzing the sample dp grid, remember there are three important points which you should pay special attention to: dp[i - 1][j - 1], dp[i - 1][j] and dp[i][j - 1]. The current dp[i][j] often depends on them.

      • If the question is also true in reverse (swap s and t), and we need to use dp[i - 1][j] or dp[i][j - 1], then we probably need to use both of them.

      • We can derive the Recurrence Formula:

        if s[i - 1] == t[j - 1]
  dp[i][j] = dp[i - 1][j - 1]
else
  dp[i][j] = dp[i][j - 1]
end

    4. Determine the dp array's traversal order

      • dp[i][j] depends on dp[i - 1][j - 1] and dp[i][j - 1], so we should traverse the dp array from top to bottom, then from left to right.

    5. Check the dp array's value

      • Print the dp to see if it is as expected.

    Complexity

    Time complexity

    O(N * M)

    Space complexity

    O(N * M)

    Solution in languages: Python C++ JavaScript Go Java C# Ruby

    Python # 

    class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        column_count = len(t) + 1
        dp = [[True] * column_count]
        for _ in s:
            dp.append([False] * column_count)

        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = dp[i][j - 1]

        return dp[-1][-1]

    C++ # 

    class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<bool>> dp(s.size() + 1, vector<bool>(t.size() + 1));
        fill(dp[0].begin(), dp[0].end(), true);

        for (auto i = 1; i < dp.size(); i++) {
            for (auto j = 1; j < dp[0].size(); j++) {
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        return dp[dp.size() - 1][dp[0].size() - 1];
    }
};

    JavaScript # 

    var isSubsequence = function (s, t) {
  const dp = Array(s.length + 1).fill().map(
    () => Array(t.length + 1).fill(false)
  )
  dp[0].fill(true)

  for (let i = 1; i < dp.length; i++) {
    for (let j = 1; j < dp[0].length; j++) {
      if (s[i - 1] == t[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else {
        dp[i][j] = dp[i][j - 1]
      }
    }
  }

  return dp.at(-1).at(-1)
};

    Go # 

    func isSubsequence(s string, t string) bool {
    dp := make([][]bool, len(s) + 1)
    columnSize := len(t) + 1
    dp[0] = slices.Repeat([]bool{true}, columnSize)
    for i := 1; i < len(dp); i++ {
        dp[i] = make([]bool, columnSize)
    }

    for i := 1; i < len(dp); i++ {
        for j := 1; j < len(dp[0]); j++ {
            if s[i - 1] == t[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = dp[i][j - 1]
            }
        }
    }

    return dp[len(dp) - 1][len(dp[0]) - 1]
}

    Java # 

    class Solution {
    public boolean isSubsequence(String s, String t) {
        var dp = new boolean[s.length() + 1][t.length() + 1];
        Arrays.fill(dp[0], true);

        for (var i = 1; i < dp.length; i++) {
            for (var j = 1; j < dp[0].length; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        return dp[dp.length - 1][dp[0].length - 1];
    }
}

    C# # 

    public class Solution
{
    public bool IsSubsequence(string s, string t)
    {
        var dp = new bool[s.Length + 1, t.Length + 1];
        for (var j = 0; j < dp.GetLength(1); j++)
            dp[0, j] = true;

        for (var i = 1; i < dp.GetLength(0); i++)
        {
            for (var j = 1; j < dp.GetLength(1); j++)
            {
                if (s[i - 1] == t[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1];
                }
                else
                {
                    dp[i, j] = dp[i, j - 1];
                }
            }
        }

        return dp[dp.GetUpperBound(0), dp.GetUpperBound(1)];
    }
}

    Ruby # 

    def is_subsequence(s, t)
  dp = Array.new(s.size + 1) do |i|
    Array.new(t.size + 1, i == 0 ? true : false)
  end

  (1...dp.size).each do |i|
    (1...dp[0].size).each do |j|
      dp[i][j] =
        if s[i - 1] == t[j - 1]
          dp[i - 1][j - 1]
        else
          dp[i][j - 1]
        end
    end
  end

  dp[-1][-1]
end
    Solution in languages: Python C++ JavaScript Go Java C# Ruby

    Other languages

    Welcome to contribute code to our GitHub repository, thanks! The location of this solution is 392. Is Subsequence.
    PreviousNext