algorithm - 搜索字符串而不考虑空格

Question

我有一个包含"a", "b", "ab", "ab c",的短语的 ArrayList "ab cd"。输入可能是"ab c"或"ab    c"。在任何一种情况下，它都应该与"ab c"ArrayList 匹配。我需要一个算法。

Answer 1

你真正要问的是如何用一个空格替换多个空格。这可能是您需要的：请参阅此问题。

Answer 2

我不知道您使用的是什么语言，但最简单的伪代码是：

f(string inString, ArrayList<string> list):
    string s = inString.removeAllWhitespace();
    foreach (string s2 in list):
        string lString = s2.removeAllWhitespace();
        if (s.equals(lString))
            return true

    return false

如果您希望它更快，请尝试以下操作：

f(string inString, ArrayList<string> list):
    foreach (string s in list):
        i1 = 0
        i2 = 0
        while (i1 < inString.length && i2 < s.length):
            if (iswhitespace(inString[i1])):
                i1++
            else if (iswhitespace(s[i2])):
                i2++
            else if (inString[i1] == s[i2]):
                i1++
                i2++
            else:
                continue foreach

        # account for trailing whitespace in both strings
        while (i1 < inString.length):
            if (!iswhitespace(inString[i1])):
                break
            i1++
        while (i2 < s.length):
            if (!iswhitespace(s[i2])):
                break
            i2++

        # strings are equal if we reached the end of both without
        # finding different characters (ignoring whitespace)
        if (i1 == inString.length && i2 == s2.length):
            return true
    return false

这将遍历具有唯一索引的每个字符串，当找到空格或匹配时递增。如果字符不匹配，则拒绝字符串并继续外循环。

这个伪代码未经测试，但应该让你知道如何去做。我建议使用删除空格路线。这是更简单的代码，不会太慢，并且可以为读者提供非常明显的线索，让他们知道你正在尝试做什么。

在大多数语言中，字符串是不可变的，因此这种替换不会影响 ArrayList 中的字符串。

Answer 3

bool hacked_compare(const string& s, const string& t){
    string::const_iterator si = s.begin(), ti = t.begin();
    while (si != s.end() && ti != t.end() && (isspace(*si) || isspace(*ti))){
        // ignore all spaces leading to next char.
        while (si != s.end() && isspace(*si))
            si++;
        while (ti != t.end() && isspace(*ti))
            ti++;
        // check for equality of two chars.
        if (*si != *ti)
            return false;
        // keep going through both strings.
        si++;
        ti++;
    }
    //if we got this far then the strings were "equivalent" or empty.
    return true;
}