LeetCode 290 Word Pattern（單詞模式）（istringstream、vector、map）（*）

LeetCode 290 Word Pattern（單詞模式）（istringstream、vector、map）（*）

翻譯

給定一個模式，和一個字符串str，返回str是否符合相同的模式。

這裡的符合意味著完全的匹配，所以這是一個一對多的映射，在pattern中是一個字母，在str中是一個為空的單詞。

例如：
pattern = "abba"， str = "dog cat cat dog" 應該返回真。
pattern = "abba"， str = "dog cat cat fish" 應該返回假。
pattern = "aaaa"， str = "dog cat cat dog" 應該返回假。
pattern = "abba"， str = "dog dog dog dog" 應該返回假。

批注：
你可以假定pattern中只包含小寫字母，在str中只包含被單個空格隔開的小寫字母。

原文

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

分析

我發現我真是越來越愛LeetCode了 ……

今天剛做了一道類似的題目：

LeetCode 205 Isomorphic Strings（同構的字符串）（string、vector、map）（*）

只不過本題是升級版的，之前是字母匹配字母，現在是字母匹配單詞了。之前的題目示例如下：

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

當時我們實現了這麼一個函數：

vector getVecOrder(string str) {
    map strM;
    int index = 0;
    vector strVec;
    for (int i = 0; i < str.size(); ++i) {
        auto iter = strM.find(str[i]);
        if (iter == strM.end()) {
            strM.insert(pair(str[i], index));
            strVec.push_back(index);
            index += 1;
        }
        else {
            strVec.push_back(strM[str[i]]);
        }
    }
    return strVec;
}

它能夠根據字符串生成序列：

For example,

Given "paper", return "01023".

Given "foo", return "011".

Given "isomorphic", return "0123245607".

現在的需求也是類似的，只不過更加升級了一點而已：

For example,

Given "dog cat cat dog", return "0110".
Given "dog cat cat fish", return "0112".
Given "Word Pattern", return "01".

所以就封裝了如下函數：

vector getVecOrderPro(string str) {
    istringstream sstream(str);
    string tempStr;
    vector strVec;
    while (!sstream.eof()) {
        getline(sstream, tempStr, ' ');
        strVec.push_back(tempStr);
    }

    map strNumMap;
    int strNumIndex = 0;
    vector orderNumVec;
    for (int i = 0; i < strVec.size(); ++i) {
        auto iter = strNumMap.find(strVec[i]);
        if (iter == strNumMap.end()) {
            strNumMap.insert(pair(strVec[i], strNumIndex));
            orderNumVec.push_back(strNumIndex);
            strNumIndex += 1;
        }
        else {
            orderNumVec.push_back(strNumMap[strVec[i]]);
        }
    }
    return orderNumVec;             
}

首先需要對整個長長的字符串進行根據空格進行切割，切割成的單個的字符串並添加到vector數組中，使用了流的相關函數。

後面的部分就和之前的一樣了，因為是個封裝好的函數了，對變量名也進行了一定的修改，前面的那個函數由此修改如下：

vector getVecOrder(string str) {
    map charNumMap;
    int charNumIndex = 0;
    vector orderNumVec;
    for (int i = 0; i < str.size(); ++i) {
        auto iter = charNumMap.find(str[i]);
        if (iter == charNumMap.end()) {
            charNumMap.insert(pair(str[i], charNumIndex));
            orderNumVec.push_back(charNumIndex);
            charNumIndex += 1;
        }
        else {
            orderNumVec.push_back(charNumMap[str[i]]);
        }
    }
    return orderNumVec;
}

最後的比較如下，因為題目沒有說pattern和str的長度一致，也就是說如果最後的索引長度不匹配了那肯定就是false了。所以多加一行：

bool wordPattern(string pattern, string str) {
    vector pattern_v = getVecOrder(pattern), str_v = getVecOrderPro(str);
    if (pattern_v.size() != str_v.size()) return false;
    for (int i = 0; i < pattern_v.size(); ++i) {
        if (pattern_v[i] != str_v[i]) return false;
    }                                                               
    return true;
}

代碼

class Solution {
public:      
    vector getVecOrder(string str) {
        map charNumMap;
        int charNumIndex = 0;
        vector orderNumVec;
        for (int i = 0; i < str.size(); ++i) {
            auto iter = charNumMap.find(str[i]);
            if (iter == charNumMap.end()) {
                charNumMap.insert(pair(str[i], charNumIndex));
                orderNumVec.push_back(charNumIndex);
                charNumIndex += 1;
            }
            else {
                orderNumVec.push_back(charNumMap[str[i]]);
            }
        }
        return orderNumVec;
    }

    vector getVecOrderPro(string str) {
        istringstream sstream(str);
        string tempStr;
        vector strVec;
        while (!sstream.eof()) {
            getline(sstream, tempStr, ' ');
            strVec.push_back(tempStr);
        }

        map strNumMap;
        int strNumIndex = 0;
        vector orderNumVec;
        for (int i = 0; i < strVec.size(); ++i) {
            auto iter = strNumMap.find(strVec[i]);
            if (iter == strNumMap.end()) {
                strNumMap.insert(pair(strVec[i], strNumIndex));
                orderNumVec.push_back(strNumIndex);
                strNumIndex += 1;
            }
            else {
                orderNumVec.push_back(strNumMap[strVec[i]]);
            }
        }
        return orderNumVec;
    }

    bool wordPattern(string pattern, string str) {
        vector pattern_v = getVecOrder(pattern), str_v = getVecOrderPro(str);
        if (pattern_v.size() != str_v.size()) return false;
        for (int i = 0; i < pattern_v.size(); ++i) {
            if (pattern_v[i] != str_v[i]) return false;
        }
        return true;
    }       
};