当前位置：网站首页>339 leetcode word rules

339 leetcode word rules

2022-04-21 23:24:00 【sp_ thirteen billion two hundred and thirty million four hundre】

Insert picture description here 

class Solution 
{
    
public:
	bool wordPattern(string pattern, string s) 
	{
    
		unordered_map<char, string> ch2str;
		unordered_map<string, char> str2ch;
		int len = s.size();
		int i = 0;
		for (auto ch : pattern)
		{
    
			if (i > len)
			{
    
				return false;
			}
			int j = i;
			while (j < len && s[j] != ' ') {
     ++j; }// Split words 
			const string& tmp = s.substr(i, j - i);
			if((ch2str.count(ch)&& ch2str[ch]!=tmp) || str2ch.count(tmp)&&str2ch[tmp]!=ch)
			{
    
				return false;
			}
			ch2str[ch] = tmp;
			str2ch[tmp] = ch;
			i = j + 1;
		}
		return i >= len;
	}
};
int main()
{
    
	Solution A;
	cout << A.wordPattern("abba","dog dog dog dog") << endl;
	return 0;
}

Time complexity ：O(n + m), among n by pattern The length of ,m by \str The length of . The average sharing time complexity of inserting and querying hash tables is O(n+m). Each character is traversed at most once

Spatial complexity ：O(n+m), among n by pattern The length of ,m by str The length of . In the worst case , We need to store pattern Each character and str Every string in

版权声明
本文为[sp_ thirteen billion two hundred and thirty million four hundre]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204212322223162.html

边栏推荐

猜你喜欢

随机推荐