Algorithm
Problem Name: 392. Is Subsequence
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).
Example 1:
Input: s = "abc", t = "ahbgdc" Output: true
Example 2:
Input: s = "axc", t = "ahbgdc" Output: false
Constraints:
0 <= s.length <= 1000 <= t.length <= 104sandtconsist only of lowercase English letters.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define IDX(ROW, COL, SZ) ((ROW + 1) * (SZ + 1) + (COL + 1))
bool isSubsequence(char* s, char* t) {
#if 0 // 260ms
int sl, tl, row, col;
bool *dp, ans = false;
if (!s || !*s) return true;
else if (!t || !*t) return false;
sl = strlen(s);
tl = strlen(t);
dp = calloc((sl + 1) * (tl + 1), sizeof(bool));
//assert(dp);
for (col = -1; col < tl; col ++) {
dp[IDX(-1, col, tl)] = true;
}
for (row = 0; row < sl; row ++) {
for (col = 0; col < tl; col ++) {
dp[IDX(row, col, tl)] = dp[IDX(row, col - 1, tl)] ||
(s[row] == t[col] && dp[IDX(row -1, col - 1, tl)]);
}
if (!dp[IDX(row, col - 1, tl)]) goto done;
}
ans = dp[IDX(sl - 1, tl - 1, tl)];
done:
free(dp);
return ans;
#else // 12ms
while (*s && *t) {
while (*t && *t != *s) {
t ++;
}
if (*t) {
s ++;
t ++;
}
}
if (*s) return false;
return true;
#endif
}
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isSubsequence(String s, String t) {
int j = 0;
for (int i = 0; i < t.length() && j < s.length(); i++) {
if (s.charAt(j) == t.charAt(i)) {
j++;
}
}
return j == s.length();
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const isSubsequence = function(s, t) {
const sl = s.length
const tl = t.length
if(sl > tl) return false
if(sl === 0) return true
let si = 0
for(let i = 0; i < tl && si < sl; i++) {
if(s[si] === t[i]> si++
}
return si === sl
};
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isSubsequence(self, s, t):
ind = -1
for i in s:
try: ind = t.index(i, ind + 1)
except: return False
return True
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0392_IsSubsequence
{
public bool IsSubsequence(string s, string t)
{
int i = 0, j = 0;
while (i < s.Length && j < t.Length)
{
if (s[i] == t[j]) i++;
j++;
}
return i == s.Length;
}
}
}
Input
Output