首页 > 其他 > 详细

LeetCode--Word Pattern

时间:2015-10-19 01:48:58      阅读:224      评论:0      收藏:0      [点我收藏+]
/** 
 * @author          johnsondu 
 * @problem         Word Pattern 
 * @url             https://leetcode.com/problems/word-pattern/ 
 * @timeComlexity   O(n) 
 * @spaceComplexity O(n) 
 * @strategy        Bfs 
 * @status          Accepted 
 */  
  
class Solution {  
public:  
    bool wordPattern(string pattern, string str) {  
        map<char, string> mp1;  
        map<string, char> mp2;  
      
        // split word  
        vector<string> vec;  
        int len = str.size();  
        string word("");  
        for(int i = 0; i < len; i ++) {  
            if(str[i] == ‘ ‘) {  
                vec.push_back(word);  
                word = "";  
            }  
            else {  
                word += str[i];  
            }  
            if(i == len - 1) {  
                vec.push_back(word);  
            }  
        }  
      
        int n = pattern.size();  
        if(vec.size() != n) return false;  
        for(int i = 0; i < n; i ++) {  
            map<char, string>::iterator mp1Ite;  
            map<string, char>::iterator mp2Ite;  
            mp1Ite = mp1.find(pattern[i]);  
            mp2Ite = mp2.find(vec[i]);  
            if(mp1Ite == mp1.end() && mp2Ite == mp2.end()) {  
                mp1[pattern[i]] = vec[i];  
                mp2[vec[i]] = pattern[i];  
            }  
            else if(mp1Ite != mp1.end() && mp2Ite != mp2.end()) {  
                if(mp1[pattern[i]] != vec[i] || mp2[vec[i]] != pattern[i])  
                    return false;  
            }  
            else return false;  
        }  
        return true;  
    }  
};  

 

LeetCode--Word Pattern

原文:http://www.cnblogs.com/Decmber/p/4890769.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!