leetcode 290. Word Pattern 使用HashMap编码

系统管理员 2022-06-08 14:27 85阅读 0赞

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.

Examples:  
pattern = “abba”, str = “dog cat cat dog” should return true.  
pattern = “abba”, str = “dog cat cat fish” should return false.  
pattern = “aaaa”, str = “dog cat cat dog” should return false.  
pattern = “abba”, str = “dog dog dog dog” should return false.  
Notes:  
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

题意很简单，使用HashMap做一次遍历，然后统一编码即可。

代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    /*
     * 做一个简单的编码替换即可
     * */
    class Solution 
    {
        
        public boolean wordPattern(String pattern, String str) 
        {
            if(pattern==null || str==null)
                return false;
            String[] s = str.split(" ");
            if(s.length!=pattern.length())
                return false;
    
            int count=0;
            StringBuilder builder1=new StringBuilder();
            Map<Character, Integer> map1=new HashMap<Character, Integer>();
            for(int i=0;i<pattern.length();i++)
            {
                if(map1.containsKey(pattern.charAt(i))==false)
                    map1.put(pattern.charAt(i), count++);
                builder1.append(map1.get(pattern.charAt(i)));
            }
    
            count=0;
            StringBuilder builder2=new StringBuilder();
            Map<String, Integer> map2=new HashMap<String, Integer>();
            for(int i=0;i<s.length;i++)
            {
                if(map2.containsKey(s[i])==false)
                    map2.put(s[i], count++);
                builder2.append(map2.get(s[i]));
            }
    
            if(builder1.toString().equals(builder2.toString()))
                return true;
            else 
                return false;
        }
    }

下面是C++的做法，就是做一个编码，对于Java很简单直接分割字符串然后编码即可，对于C++需要这么做，哈哈很棒的做法

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        bool wordPattern(string p, string str) 
        {
            stringstream ss(str);
            vector<string> all;
            string tmp = "";
            while (ss >> tmp)
                all.push_back(tmp);
    
            if (all.size() != p.length())
                return false;
    
            string a = "", b = "";
            map<char, int> mmp1;
            for (int i = 0,count=0; i < p.length(); i++)
            {
                if (mmp1.find(p[i]) == mmp1.end())
                    mmp1[p[i]] = count++;
                a += mmp1[p[i]];
            }
    
    
            map<string, int> mmp2;
            for (int i = 0, count = 0; i < all.size(); i++)
            {
                if (mmp2.find(all[i]) == mmp2.end())
                    mmp2[all[i]] = count++;
                b += mmp2[all[i]];
            }
    
            return a == b;
        }
    };