程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 290 Word Pattern(單詞模式)(istringstream、vector、map)(*)

LeetCode 290 Word Pattern(單詞模式)(istringstream、vector、map)(*)

編輯:C++入門知識

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved