Leetcodeブラシ87-409.最长回文串(C++详细解法!!)

Come from : [https://leetcode-cn.com/problems/word-pattern/]
290. Word Pattern

1.Question

2.Answer

3.私の収穫

1.Question
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 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

Note:

You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

2.Answer
easyタイプタイトル(easyではないような気がします).文字ハッシュ表を使います.以下は構想ですが、私のコードにも詳細な注釈があり、皆さんに共有します.
例を分析し、法則をまとめる.

strはpattern数と同じ

str単語を1つ解体する場合、strに既に単語が出現する場合、その単語に対応するpattern文字は、かつて対応していたpattern文字

でなければならない.

str単語を分解する場合、strに単語が現れない場合、その単語に対応するpattern文字が現れないことは明らかでなければならない.これはその強いマッピング関係であり、本題ではstr---patternのマッピング

を考慮する.
アルゴリズムの考え方:str=“dog cat*”pattern=“abb?”

単語strからpattern’へのハッシュマッピングを設定し、配列used[128]を使用してpattern文字が

を使用するかどうかを記録する.

strを巡回し、スペースに従って単語を分割するとともに、patternを移動するポインタに対応し、ハッシュテーブルに単語が現れなかった場合:patternのusedが使用された場合、falseは現在の単語がpatternにマッピングされ、usedタグが使用されない場合、現在のハッシュテーブルの単語マッピングがpattern文字を指していない場合、false

str pattern数がfalseに一致しないのは全体的に言えば、2つの集合を同時に遍歴し、マッピングとして現れず、判断として現れたことがあり、すべて遍歴してから数を見ることだ.

MACコードは以下の通りである.

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        map<string, char> word_map;
        char used[128] = {0}; //     pattern  
        int pos = 0;  //     ，   pattern
        string word;  //      
        str.push_back(' '); //       ，      
        
        for(int i = 0; i < str.length(); ++i)
        {
            if(str[i] == ' ')
            {
                //                 ：
                // 1    pattern   str    ， ：       ，pattern  。    ：str=“dog fish” pattern=“a”
                if(pos == pattern.length())
                {
                    return false;
                }
                // 2.                
                if(word_map.find(word) == word_map.end())
                {
                    // 2.1             .      ，   false
                    if(used[pattern[pos]])  //    ：str=“dog cat cat fish”， pattern=“abba”
                    {
                        return false;
                    }
                    // 2.2       ，       
                    word_map[word] = pattern[pos];
                    used[pattern[pos]] = 1;
                }
                else //3.               
                {
                    // 3.1     word       ，      pattern   ,     fasle
                    if(word_map[word] != pattern[pos])
                    {
                        return false;  //    ：str=“dog cat cat fish”， pattern=“abca”
                    }
                }
                word = "";  //            ，   word
                ++pos;      //   pattern        
            }
            else
            {
                word += str[i];
            }
        }
        //4      pattern  。     ：str=“dog”， pattern=“aab”
        if(pos != pattern.length())
        {
            return false;
        }
        return true;
    }
};

3.私の収穫
感覚はやはり系統的に知識を身につけなければならない...例えば今回のハッシュ表day 2...系統的に勉強してから、もっと上手に運用することができます.
2019/5/26胡雲雲は南京で87