Searching strings irrespective of whitespace

Question

I have an ArrayList of phrases containing "a", "b", "ab", "ab c", "ab cd". The input might be "ab c" or "ab    c". In either cases it should match with "ab c" from the ArrayList. I need an algorithm for it.

Answer 1

What you're really asking is how to replace the multiple spaces with a single space. This might be what you need:See this question.

Answer 2

I don't know what language you're using, but the simplest pseudocode is:

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

If you want it to be faster, try something like this:

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

This will go iterate through each string with unique indices, incrementing when either whitespace is found or a match. If the characters don't match, the string is rejected and the outer loop is continued.

This pseudocode is untested, but should give you an idea of how to do it. I recommend going the remove whitespace route. It's much simpler code, not too slow, and gives the reader very obvious clues as to what you're trying to do.

In most languages, strings are immutable, so doing this replacement won't affect the strings in the 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;
}