搜索字符串，不考慮空白

Question

我有一個包含"a","b","ab","ab c", "ab cd"的短語ArrayList。 輸入可能是"ab c"或"ab    c"。在任何情況下，它都應該與ArrayList中的"ab c"匹配。我需要一個算法。

Answer 1

我不知道你使用的是什麼語言，但最簡單的僞代碼：

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 2

你真正要問的是如何用一個空格替換多個空格。這可能是你所需要的：See this question.

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; 
}