290.Word Pattern词语匹配

qlmx
qlmx
qlmx
50
文章
2
评论
2020年2月15日00:20:51 评论 908阅读3分31秒

290. Word Pattern(词语匹配)

1 问题描述

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.

已知字符串pattern与字符串str,确认str是否与pattern匹配。str与pattern匹配代表字符 串str中的单词pattern中的字符一一对应。(其中pattern中只包含小写字符,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

2 C++实现

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        map<string, char> word_map;
        char used[128] = {0};
        int pos = 0;
        string word; //存储未知变量
        str.push_back(' '); //为了读取最后一个单词
        for(int i=0; i<str.length(); i++) {
            if(str[i] == ' ') {
                if(pos == pattern.length())
                    return false;

                if(word_map.find(word) == word_map.end()) {
                    if(used[pattern[pos]])
                        return false;
                    word_map[word] = pattern[pos];
                    used[pattern[pos]] = 1;
                }
                else {
                    if(word_map[word] != pattern[pos])
                        return false;
                }
                pos++;
                word = "";
            }
            else {
                word += str[i];
            }
        }
        if (pos != pattern.length()){
            return false;
        }
        return true;
    }
};
继续阅读
  • 我的微信小程序
  • 这是我的微信小程序扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin
qlmx
  • 本文由 发表于 2020年2月15日00:20:51
  • 除非特殊声明,本站文章均为原创,转载请务必保留本文链接
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: