求解答下面这道题的完整代码(用C++),目前不太会用map,所以希望能不用就不用map,谢谢谢谢

2025-03-18 05:04:55
推荐回答(1个)
回答1:

#include 
#include 
#include 
#include 

bool match(const std::string &pattern, const std::string &str)
{
    bool result = true;
    std::string word;
    std::vector  word_list;
    size_t size = pattern.size();
    word_list.reserve(size);
    
    std::istringstream read(str);
    while (read >> word) word_list.push_back(word);
    
#if DEBUG
    assert(size == word_list.size());
#endif

    for (int i = 0; i < size; i ++)
    {
        for (int j = i + 1; j < size; j ++)
        {
            bool pattern_match = pattern[i] == pattern[j];
            bool word_match = word_list[i] == word_list[j];
            if (pattern_match != word_match)
            {
                result = false;
            }
        }
    }
    
    return result;
}

void checkAndPrintResult(const std::string &pattern, const std::string &str)
{
    std::cout << "pattern = \"" << pattern << "\", str = \"" << str << "\" should return "
        << (match(pattern, str) ? "true" : "false") << ".\n";
}

int main()
{
    checkAndPrintResult("abba", "dog cat cat dog");
    checkAndPrintResult("abba", "dog cat cat fish");
    checkAndPrintResult("aaaa", "dog cat cat dog");
    checkAndPrintResult("abba", "dog dog dog dog");
    
    return 0;
}
  1. 图省事的做法,时间复杂度 O((pattern.size()^2), 不是很优化,但您未在描述中提出数据范围等。

  2. 未使用 map