是子序列Leetcode解决方案  


难度级别 易得奖学金
经常问 土砖 亚马逊 彭博 Facebook 谷歌 微软 Pinterest Yandex的
算法 编码 动态编程 贪婪 访谈 面试准备 力码 力码解决方案

问题陈述  

在这个问题上,我们得到两个不同的 字符串。 目的是找出第一个字符串是否为 子序列 第二。

例子

first string = "abc"
second string = "mnagbcd"
true
first string = "burger"
second string = "dominos"
false

是子序列Leetcode解决方案Pin

方法(递归)  

显而易见,我们可以从字符串的末端开始对其进行匹配。 如果最后一个字符串中的字符匹配,那么我们就可以简化子问题,确定是否可以从原始字符串中获得两个字符串 after 删除其最后一个字符时,遵循子序列标准。 如果结尾字符不匹配,我们只删除第二个字符串的最后一个字符以在其中搜索。

可以通过传递字符串的索引作为参数来比较每次递归调用中的字符来递归地完成此操作。

算法

  1. 索引 表示第一个字符串的最后一个索引,并且表示递归调用中第二个字符串的最后一个索引
  2. If 我 == -1:
    1. 我们已经完全遍历了第一个字符串,返回 true
  3. If j == -1:
    1. 我们已经完全遍历了第一个字符串,返回 false
  4. If first_string [i] == second_string [j]:
    1. 用索引调用递归函数 (i – 1,j – 1)
  5. 返回带有索引的递归函数的结果 (i,j – 1)

Is子序列Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

string S , T;

bool checkSubsequence(int i , int j)
{
    if(i == -1)
        return true;
    if(j == -1)
        return false;
    if(S[i] == T[j])
        return checkSubsequence(i - 1 , j - 1);
    return checkSubsequence(i , j - 1);
}

bool isSubsequence(string s, string t)
{
    S = s , T = t;
    return checkSubsequence((int)s.size() - 1 , (int)t.size() - 1);
}

int main()
{
    string s = "abc";
    string t = "mnagbcd";

    cout << (isSubsequence(s , t) ? "true" : "false") << '\n';
    return 0;
}

Java程序

class is_subsequence
{
    static String S , T;

    public static void main(String args[])
    {
        String a = "abc" , b = "mnagbcd";
        System.out.println((isSubsequence(a , b) ? "true" : "false"));
    }

    static boolean checkSubsequence(int i , int j)
    {
        if(i == -1)
            return true;
        if(j == -1)
            return false;
        if(S.charAt(i) == T.charAt(j))
            return checkSubsequence(i - 1 , j - 1);
        return checkSubsequence(i , j - 1);
    }

    static boolean isSubsequence(String s, String t)
    {
        S = s;
        T = t;
        return checkSubsequence((int)s.length() - 1 , (int)t.length() - 1);
    }
}
true

Is子序列Leetcode解决方案的复杂性分析

时间复杂度

O(最小(N,M)) 因为我们需要重复执行,直到遍历两个字符串中的任何一个为止。 N 以及 M 是字符串的长度。

参见
第N个Tribonacci号码Leetcode解决方案

空间复杂度

O(最小(M,N) 在最坏的情况下,由于递归调用。

进场(两分球)  

我们可以通过维护两个指针来反复使用以上技术 i 以及 存储各个字符串的最后一个索引。 我们可以迭代直到它们中的任何一个变为零为止。 如果 i (第一个字符串的指针)大于或等于0,我们无法完全遍历第一个字符串,因此,它不是第二个字符串的子序列。 否则,我们返回true。

算法

  1. 初始化两个指针 我和j 存储两个字符串的最后一个索引。
  2. i> = 0且j> = 0:
    1. 如果first_string [i] == second_string [j]:
      1. i-, j -
    2. 其他
      1. j -
  3. If i > = 0:
    1. 退货 false
  4. 退货 true

Is子序列Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

string S , T;

bool isSubsequence(string s , string t)
{
    int i = s.size() , j = t.size();

    i-- , j--;

    while(i >= 0 && j >= 0)
    {
        if(s[i] == t[j])
            i-- , j--;
        else
            j--;
    }

    if(i >= 0)
        return false;
    return true;
}

int main()
{
    string s = "abc";
    string t = "mnagbcd";

    cout << (isSubsequence(s , t) ? "true" : "false") << '\n';
    return 0;
}

Java程序

class is_subsequence
{
    static String S , T;

    public static void main(String args[])
    {
        String a = "abc" , b = "mnagbcd";
        System.out.println((isSubsequence(a , b) ? "true" : "false"));
    }

    static boolean isSubsequence(String s , String t)
    {
        int i = s.length() , j = t.length();

        i--;
        j--;

        while(i >= 0 && j >= 0)
        {
            if(s.charAt(i) == t.charAt(j))
            {
                i--;
                j--;
            }
            else
                j--;
        }

        if(i >= 0)
            return false;
        return true;
    }
}
true

Is子序列Leetcode解决方案的复杂性分析

时间复杂度

O(最小(M,N)) 当我们不断迭代直到 我或j 变为零。 M和N是字符串的长度。

空间复杂度

O(1) 因为我们在内存中使用恒定的空间。

1