290 Word Pattern 單詞規(guī)律
Description:
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.
Example :
Example 1:
Input: pattern = "abba", str = "dog cat cat dog"
Output: true
Example 2:
Input:pattern = "abba", str = "dog cat cat fish"
Output: false
Example 3:
Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false
Example 4:
Input: pattern = "abba", str = "dog dog dog dog"
Output: false
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.
題目描述:
給定一種規(guī)律 pattern 和一個(gè)字符串 str 剩晴，判斷 str 是否遵循相同的規(guī)律峭火。
這里的 遵循 指完全匹配挠将，例如矫夯， pattern 里的每個(gè)字母和字符串 str 中的每個(gè)非空單詞之間存在著雙向連接的對(duì)應(yīng)規(guī)律肚邢。
示例 :
示例 1:
輸入: pattern = "abba", str = "dog cat cat dog"
輸出: true
示例 2:
輸入:pattern = "abba", str = "dog cat cat fish"
輸出: false
示例 3:
輸入: pattern = "aaaa", str = "dog cat cat dog"
輸出: false
示例 4:
輸入: pattern = "abba", str = "dog dog dog dog"
輸出: false
說(shuō)明:
你可以假設(shè) pattern 只包含小寫字母环肘， str 包含了由單個(gè)空格分隔的小寫字母此叠。
思路:
用 split()函數(shù)將字符串按空格分割成字符串?dāng)?shù)組
采用 map記錄單詞和 pattern中的字符的對(duì)應(yīng)關(guān)系
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)
代碼:
C++:
class Solution
{
public:
bool wordPattern(string pattern, string str)
{
const vector<string>& list = split(str, ' ');
if (list.size() != pattern.size()) return false;
map<string, char> dict1;
map<char, string> dict2;
for (int i = 0; i < list.size(); i++)
{
const string& s = list[i];
if (dict1.find(s) != dict1.end())
{
char tmp = dict1[s];
if (tmp != pattern[i]) return false;
}
else
{
if (dict2.size() and dict2.find(pattern[i]) != dict2.end()) return false;
dict1.insert(make_pair(s, pattern[i]));
dict2.insert(make_pair(pattern[i], s));
}
}
return true;
}
private:
vector<string> split(string& str,const char a)
{
vector<string> strvec;
string::size_type pos1, pos2;
pos2 = str.find(a);
pos1 = 0;
while (string::npos != pos2)
{
strvec.push_back(str.substr(pos1, pos2 - pos1));
pos1 = pos2 + 1;
pos2 = str.find(a, pos1);
}
strvec.push_back(str.substr(pos1));
return strvec;
}
};
Java:
class Solution {
public boolean wordPattern(String pattern, String str) {
char[] chars = pattern.toCharArray();
String[] strs = str.split(" ");
if (chars.length != strs.length) return false;
Map<Character, String> map = new HashMap<>();
for (int i = 0; i < chars.length; i++) {
if (map.containsKey(chars[i])) {
if (!map.get(chars[i]).equals(strs[i])) return false;
} else if (map.containsValue(strs[i])) return false;
map.put(chars[i], strs[i]);
}
return true;
}
}
Python:
class Solution:
def wordPattern(self, pattern: str, str: str) -> bool:
str = str.split(' ')
if not pattern or not str or len(set(str)) != len(set(pattern)) or len(str) != len(pattern):
return False
dict = {}
for i in range(len(str)):
if pattern[i] in dict:
if dict[pattern[i]] == str[i]:
continue
else:
return False
dict[pattern[i]] = str[i]
return True
