在字符串中检查一组字符

Question

给定一个字符串，如何检查一组字符是否存在于该字符串中（并找到它们的位置），使得这些字符需要按照相同的顺序，但不必连续。

例如，对于字符串"INEEDTOGETAHAIRCUT"和要查找的集合{'O','E','G','T'}。

谢谢。

（附言 - 我已经尝试了蛮力方法，但它很糟糕，并且不起作用！）

- Biscuit128

---

问题不清楚。“只要它们彼此相随，它们可以以任何顺序出现。”这似乎是自相矛盾的。 - David Heffernan

好的，字符不能出现在字符串的任何位置，它们必须是连续的，但顺序并不重要 - 嗯，我可以理解为什么这可能听起来不清楚。我不确定还有什么其他方式可以解释。 - Biscuit128

所以你需要在测试字符串中找到用尽集合{'O','E','G','T'}的4个连续字符。 - David Heffernan

允许值为“OOOO”吗？还是您想搜索O、E、G和T的任意组合？ - Fischermaen

不允许使用OOOO，但是允许使用满足OEGT集合的4个连续字符。 - Biscuit128

Answer 1

为什么不使用更简单的东西，只需两行代码即可检查你所需要的内容呢？

string strCompare = "INEEDTOGETAHAIRCUT";
string strStringContains = ""AHRI"; 
var matchingString = strCompare.IndexOfAny(strStringContains.ToCharArray()) != -1;
then wrap the matchingString in an if(matchingString){ } // should return true or false

- MethodMan

Answer 2

如果你在使用中添加了 System.Linq，你可以这样做：

"INEEDTOGETAHAIRCUT".ToCharArray().Any(c => c=='O' || c=='E' || c=='G' || c=='T');

或者编写一个新的扩展方法来接受字符数组作为参数。 要以任何顺序拥有任何“序列”中的字符，可以这样做：

public static class MyExtensions
{

    public static bool ContainsAnySequenceOf(this String str, List<char> charArray)
    {
        foreach (char c in charArray)
        {
            if (str.ToCharArray().Any(x => x == c))
            {
                charArray.Remove(c);
                return str.Substring(str.IndexOf(c), Math.Min(str.Length - str.IndexOf(c), charArray.Count)).ContainsAnySequenceOf(charArray);
            }
        }
        return false;
    }
}

然后像这样调用它：

"INEEDTOGETAHAIRCUT".ContainsAnySequenceOf(new List<char> {'O','E','G','T'});

- Andrea Colleoni

---

啊，那很完美，但不幸的是我需要知道具体位置而不仅仅是真或假。我真的应该提到这个 :/ - Biscuit128

好的。我现在更好地理解了你的问题，并编辑了我的答案以实现这一点。 - Andrea Colleoni

Answer 3

假设我不完全确定你所说的“字符相互跟随”的含义，这里提供一种可能的方法：生成所有可能的字符序列排列并搜索排列。

using System;
using System.Collections.Generic;
class Program {

    static IEnumerable<string> GetPermutations(string value) {
        if (value.Length == 1) {
            yield return value;
        } else {
            for (int i = 0; i < value.Length; ++i) {
                string a = value[i].ToString();
                foreach (string b in GetPermutations(value.Remove(i, 1))) {
                    yield return a + b;
                }
            }
        }
    }

    static void Main(string[] args) {

        string test = "INEEDTOGETAHAIRCUT";
        string chars = "OEGT";
        foreach (string to_find in GetPermutations(chars)) {
            int i = test.IndexOf(to_find);
            if (i != -1) {
                Console.WriteLine("Found {0} at index {1}", to_find, i);
            }
        }
    }
}

- Paolo Tedesco

---

我的唯一问题是复杂度的顺序。但对于提问者来说，这可能并不重要。 - Akron

Answer 4

这里是一个非常不优雅的老派方法来解决这个问题。虽然我相信代码中有些地方可以更高效，但它避免了枚举搜索集合的所有排列（就像你接受的答案所做的那样）。这样做可能会变得很昂贵。

static bool matchesPermutation(string test, string search)
{
    string remaining = search;
    for (int i = 0; i < test.Length; i++)
    {
        int pos = remaining.IndexOf(test[i]);
        if (pos == -1)
            return false;
        else
            remaining = remaining.Remove(pos, 1);
    }
    return true;
}

static int findPermutation(string test, string search)
{
    for (int i = 0; i < test.Length-search.Length+1; i++)
        if (matchesPermutation(test.Substring(i, search.Length), search))
            return i;
    return -1;
}

static void Main(string[] args)
{
    string test = "INEEDTOGETAHAIRCUT";
    string search = "AHRI";
    int foundPos = findPermutation(test, search);
    Console.WriteLine(foundPos);
    if (foundPos != -1)
        Console.WriteLine(test.Substring(foundPos, search.Length));
}

- David Heffernan

Answer 5

如果我正确理解了您的问题：

您可以使用 String.IndexOfAny() 找到序列的第一个字符。

然后迭代字符串中的以下字符，以检查它们是否包含在合法字符集中。对于您从列表中找到的每个字符（包括您找到的第一个字符），请将其从可以跟随的合法字符列表中删除，以禁止重复。

如果遇到非法字符，则文本不匹配，请返回此算法的开头以处理字符串的剩余部分。

如果您连续找到所有合法字符，则您已经得到了结果。

- Jason Williams

---

返回从我的集合中任何字符第一次出现的索引，与它们全部一起出现的第一次出现相对立，如果这有意义的话？ - Biscuit128

但这并不满足“字符相互跟随”的需求。 - Fischermaen

抱歉，问题有些不清楚。我的回答已经更新，提供更多帮助。 - Jason Williams