我刚开始学习，对如何做这个完全没有头绪。
我想要检查一个字符串是否包含另一个更小的字符串，并且如果这个字符串按顺序包含了另一个字符串中的字母，则返回true。
我不确定如何确保第二个字符串的字母按顺序排列，即使它们之间有其他字母。
例如，“chemistry”将针对字符串“hit”返回true。
但是对于字符串“him”，将返回false。
非常感谢任何帮助。
编辑：谢谢，我把“子字符串”这个词改成了“字符串”。正如我所说，我刚开始学习，还不知道它意味着别的什么。我真的很感激所有的帮助。这将让我朝着正确的方向前进。
一般的方法是遍历较长的字符串（"chemistry"），始终跟踪从较短字符串（"hit"）中需要的下一个字符的索引（首先为0，然后是1当你找到h时，接着是2当你找到i时，最后当你找到t时就完成了）。例如：
public static boolean containsSubsequence(
final String sequence, final String subsequence) {
if (subsequence.isEmpty()) {
return true;
}
int subsequenceIndex = 0;
for (int i = 0; i < sequence.length(); ++i) {
if (sequence.charAt(i) == subsequence.charAt(subsequenceIndex)) {
++subsequenceIndex;
if (subsequenceIndex == subsequence.length()) {
return true;
}
}
}
return false;
}
因为您没有发布任何代码，所以我将解释我的做法。
s1.charAt(i) == s2.charAt(j)，这种情况对于 i = 1 （化学中的第二个字符是h）成立。然后你增加，现在又再次增加，直到你碰到一个“i”（i=4）。如果最后满足j==s2.length()，则第二个字符串包含在第一个字符串中作为一个子序列。请注意，在这里 - 与更复杂的问题（例如测试第二个字符串是否真的是一个“子字符串”）不同，贪心策略有效，这意味着您不必担心与第二个字符串中的当前字符匹配的多个出现之一;您总是可以“贪婪地”选择您看到的第一个。String pat =“.*h.*i.*t.*”，并测试s1.matches(pat)。public class SearchString {
public static void main(String[] args) {
String searchSpace = "this is where to search?";
String needle = "tweus?";
char[] chars = needle.toCharArray();
int index = 0;
boolean found = true;
int startIndex = 0;
while (found && index < chars.length){
searchSpace = searchSpace.substring(startIndex);
startIndex = searchSpace.indexOf(chars[index]);
found = (startIndex != -1);
index++;
}
if (index==chars.length && found){
System.out.println("Found it");
} else {
System.out.println("Nothing here");
}
}
}
基于@ruakh的解决方案稍作修改后得到以下答案：
public static boolean containsSubsequence(final String sequence, final String subsequence) {
if (Objects.requireNonNull(sequence).isEmpty() || Objects.requireNonNull(subsequence).isEmpty() || subsequence.length() > sequence.length()) {
return false;
}
int index = 0;
for (int i = 0; i < sequence.length(); i++) {
if (sequence.charAt(i) == subsequence.charAt(index) && ++index == subsequence.length()) {
return true;
}
}
return false;
}
Objects.requireNonNull() 是从Java 7开始的，如果你不在Java 7上，请记得替换成类似的东西（来自Apache Commons's StringUtils？）。验证假定返回false适用于空序列或子序列，否则您可能需要考虑抛出类似IllegalArgumentException的内容。
为了紧凑，两个if语句已经合并成一个单独的子句。
编辑：
如果您对数学倾向，或者遵循@ruakh的原始解决方案，则任何序列都应包含一个空子序列。我上面的代码之所以这样做是因为我喜欢将空参数想象为一种无效参数，因此返回false。它真的取决于该方法的使用方式以及空参数的“严重程度”。
我知道这个问题是关于Java的。但是只是为了参考，这里有一个C语言版本的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int find_str_in_str(const char* const base, const char* const sub)
{
int base_len = strlen(base);
int sub_len = strlen(sub);
char *tmp_sub = NULL;
/* allocate enough mem for the max string length */
if(base_len > sub_len) {
tmp_sub = malloc(base_len + 1);
} else {
tmp_sub = malloc(sub_len + 1);
}
if(NULL == tmp_sub) {
fprintf(stderr, "Runtime error (malloc)\n");
exit(1);
}
int i = 0;
int j = 0;
for(; i < sub_len; i++) {
for(; j < base_len; j++) {
if(base[j] == sub[i]) {
tmp_sub[i] = base[j];
/* the first occurance was found */
break;
}
}
}
tmp_sub[i++] = '\0';
if(0 == strcmp(sub, tmp_sub)) {
free(tmp_sub);
return 1;
} else {
free(tmp_sub);
return 0;
}
}
int main(int argc, char **argv)
{
if(argc < 3) {
fprintf(stderr, "Usage: %s %s %s\n", argv[0], "base", "derived");
return EXIT_FAILURE;
}
if(1 == find_str_in_str(argv[1], argv[2])) {
printf("true\n");
} else {
printf("false\n");
}
return EXIT_SUCCESS;
}
编译命令：gcc -Wall -Wextra main.c -o main
主函数自身 ELF
主函数化学尝试
主函数化学打击
主函数化学计时