数据结构基础day7

题目：290. 单词规律

解法：双映射

即找双向映射，满足str2ch和ch2str双映射返回true，否则返回false
时间复杂度为O(m+n)，n为pattern的长度，m是s的长度，插入和查询哈希表的均摊时间复杂度为O(m+n)，每个字符最多遍历一遍。
空间复杂度为O(m+n)，n为pattern的长度，m是s的长度，最坏情况下存储pattern和s中的每一个字符。

class Solution {
public:bool wordPattern(string pattern, string s) {unordered_map<string, char> str2ch;	//str2ch的映射unordered_map<char, string> ch2str;	//ch2str的映射int m = s.size();	//s的长度int i=0;	//遍历指针for(char ch:pattern){	//根据pattern长度进行遍历if(i>=m) return false;	//pattern仍然存在字符可以遍历，而遍历指针已经超过m，即pattern长度大于s长度，返回falseint j=i;	//子串遍历指针while(j<m&&s[j]!=' ') ++j;	//选择子串string temp = s.substr(i,j-i);	//截取子串，注意substr的用法，substr(i,j)，从第i个位置开始截取j项字符if(str2ch.count(temp)&&str2ch[temp]!=ch){	//判断str2ch映射return false;}if(ch2str.count(ch)&&ch2str[ch]!=temp){		//判断ch2str映射return false;}str2ch[temp]=ch;	//更新映射ch2str[ch]=temp;i=j+1;	//更新遍历指针，这里j指在空格处，所以i要+1，指向下一个子串的起始位置}// return true;return i>=m;	//此时已经出了pattern的循环，意味着pattern字符遍历结束，此时如果i小于m，意味着s没有遍历结束，即pattern长度小于s长度，返回false，否则两者遍历结束返回true}
};

题目：763. 划分字母区间

主要是要找子串的头尾指针，由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。更新当前片段的end，然后截取子串长度。

解法：贪心

class Solution {
public:vector<int> partitionLabels(string s) {int last[26];	//存储每个字符最后一次出现的下标位置int n = s.size();for(int i=0; i<n; ++i){last[s[i]- 'a'] = i;}int start = 0, end = 0;	//每个子串的头尾指针vector<int> ans;	//存储子串长度for(int i=0; i<n; ++i){	//遍历每个字符end = max(end, last[s[i]-'a']);	//更新end，取当前end和当前字符最后一次出现位置的最大值if(i==end){	//如果i已经遍历到end，说明子串确定ans.push_back(end-start+1);	//存储子串长度start = end + 1;	//更新下一个子串的起始位置}}return ans;}
};