检查字符串是否按顺序包含子字符串的字符序列,但不一定紧挨着彼此

Question

给定两个字符串,如果第一个字符串按顺序包含第二个字符串的字符序列,则返回true,但不一定紧挨着彼此.

例如,字符串:"我很饿,现在想要食物",子串:"mto".o在句子中t之前出现的子字符串不计算,它们必须按顺序排列,但不一定紧挨着彼此.

我不是在寻找代码,一般来说你会如何解决这个问题!

Answer 1

通常当您第一次遇到问题时,在考虑如何对计算机进行编程之前,应该先评估自己如何解决问题.

如果您尝试自己解决您的示例问题,您很可能从第二个字符串中的第一个字符'm'开始,并在字符串中搜索该字符的第一个外观.一旦在第3个索引位置找到'm',您就可以从第4个索引开始评估,找到子字符串中的下一个字母.您将继续评估,直到发生以下两种情况之一:

1. 你找不到其中一个字母.这意味着结果是false.
2. 你的子字符串中没有字母.这意味着结果是true.

如果您了解如何自己解决问题,那么只需将解决方案分解为步骤即可.

你没有要求它,但是在它失败的情况下它会更清楚,这是一个解决问题的简单方法:

public static boolean sub(String string, String substring) {
    // Keep track of our position in the string.
    int index = 0;

    // Iterate through all of the characters in the substring.
    for (char character : substring.toCharArray()) {
        // Find the current character starting from the last character we stopped on.
        index = string.indexOf(character, index);
        // If the method returned -1, the character was not found, so the result is false.
        if (index == -1)
            return false;
    }

    // If we reach this point, that means all characters were found, so the result is true.
    return true;
}

Answer 2

一个简单的实现就像

从一侧到另一侧遍历两个字符串。如果找到匹配的字符，则在两个字符串中继续前进。否则只在 s2 中前进。

bool isSubSequence(std::string s1, std::string s2) {
    int j = 0;
    for (int i = 0; i < s2.length() && j < s1.length(); ++i)
        if (s1[j] == s2[i])
            ++j;
    return j == s1.length();
}

Answer 3

您必须一次搜索字符串一个子字符串字符。既然你说你不需要代码，我将尝试用文字解释如何实现（并提供一些 Java API 调用供参考）。

对于子字符串中的每个字符，查找该字符在字符串中第一次出现的位置（在本例中为“m”，然后是“t”，然后是“o”）。您可以通过调用 来完成此操作String.indexOf(String char)。跟踪找到该字符的索引，当您在 String 中搜索下一个字符（在本例中为“t”）时，请使用 查找从该索引开始的 String 子集String.substring(idx, -1).indexOf(String char)。-1 将从先前找到的字符 ('m') 的索引开始搜索，直到字符串末尾。

继续迭代 Substring 的字符，将会发生以下两种情况之一。首先，你不会在 String 的子集中找到该字符，这意味着 Substring 不按顺序存在。第二种可能性是，您将到达子字符串的末尾，并且所有字符都将按顺序找到。