290. Word rules

Given a pattern and a string str, judge whether str follows the same rule.

The ， here refers to complete matching. For example, there is a corresponding law of two-way connection between each letter in pattern ， and each non empty word in string ， str ，.

Example 1:

Input: pattern = "Abba", STR = "dog cat dog"
Output: true

Example 2:

Input: pattern = "Abba", STR = "dog cat fish"
Output: false

Example 3:

Input: pattern = "AAAA", STR = "dog cat dog"
Output: false

Example 4:

Input: pattern = "Abba", STR = "dog dog"
Output: false

explain:
You can assume that str pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Original idea:

My initial idea was to identify words before corresponding types

Train of thought correction:

Contrary to my original idea, it is to use the type to correspond to the string, and then use each string to correspond to the character (bidirectional)

1. Hash table
Use the hash table to record the string corresponding to each character and the character corresponding to each string
Enumerate the pairing process of each pair of characters and strings, and constantly update the hash table
If a conflict occurs, the given input does not satisfy the bijection relationship.
Enumerate each character in the pattern and use double pointers to evenly find the string corresponding to the character in str
Each time we determine the combination of a character and a string, we check whether there is a conflict. Finally, we check whether the two strings are compared

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<string, char> str2ch;
        unordered_map<char, string> ch2str;
        int m = str.length(); //Length of string
        int i = 0;//Pointer
		//Traversal pattern
        for (auto ch : pattern) { 
            if (i >= m) {  //The length of pattern is greater than m
                return false;
            }
            int j = i;
            while (j < m && str[j] != ' ') j++;
            const string &tmp = str.substr(i, j - i);//To copy a substring, it is required to start at the specified position and have the specified length
            if (str2ch.count(tmp) && str2ch[tmp] != ch) {  //The count function counts the number of times a value appears in a certain range
                return false;
            }
            if (ch2str.count(ch) && ch2str[ch] != tmp) {
                return false;
            }
            str2ch[tmp] = ch;
            ch2str[ch] = tmp;
            i = j + 1;
        }
        return i >= m;
    }
};

  2.stringstream
(1) Two map s are defined. Why are they defined? Prevent outputting true when [aaaa] and [cat dog cat], [abba] and [cat cat cat cat]
(2) You can automatically output phrases with stringstream
(3) Judgment:! (ss > > s) judge whether the pattern length is greater than the str length, and assign the string in the ss container to s
(4) Judgment: (map. Count (c) = = 1 & & map [C]= s) || (rmap.count(s) == 1 && rmap[s] != c) ) to determine whether it matches
(5) Judgment: (SS > > s)? False: true determines whether the str length is greater than the pattern length

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char, string> map;
        unordered_map<string, char> rmap;
        stringstream ss(str);
		string s;
        for(char c : pattern) {
            if(!(ss >> s) || (map.count(c) == 1 && map[c] != s) || (rmap.count(s) == 1 && rmap[s] != c)) return false;
            map[c] = s;
			rmap[s] = c;
        }
        return (ss >> s) ? false : true;
    }
};

763. Division of letter interval

The string S consists of lowercase letters. We should divide the string into as many segments as possible, and the same letter can appear in one segment at most. Returns a list representing the length of each string fragment.

Example:

Input: S = "ababcacadefegdehijhklij"
Output: [9,7,8]

Explanation:
The division results are "ababcbaca", "defegde", "hijhklij".
Each letter can appear in at most one segment.
Like "ababcacadefegde", the division of "hijhklij" is wrong because the number of fragments divided is small.
Tips:

The length of S is between [1, 500].
S contains only lowercase letters' a 'to' z '.

Idea:

//Traverse the string and record the position of the last occurrence

//Change the array corresponding to each letter to the number of the last occurrence

//Traverse the position array. When the same number with the farthest interval is found, it is the segmentation point

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27] = {0}; // I is the character, and hash[i] is the last position of the character
        for (int i = 0; i < s.size(); i++) { // Count the last position of each character
            hash[s[i] - 'a'] = i;//The subscript must be an integer, and because it is a lowercase letter, char - 'a' becomes an integer corresponding to a lowercase letter
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < S.size(); i++) {
            right = max(right, hash[s[i] - 'a']); // Find the farthest boundary where the character appears
            if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};