Algorithm to Check if A String Matches a Pattern

  • 时间:2020-10-09 18:35:39
  • 分类:网络文摘
  • 阅读:94 次

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

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

Check Pattern Using Hash Maps

We can use two hash maps to associate with pattern to words and vice versa. Spliting the string by delimiter space, and go through each token/word to see if it matches the existing character. If not, we store the new mapping. If there is a mapping already – we check if it is the same and return false immediately when mapping does not match.

Some edge cases are to be handled – checking if the pattern sizes same as the number of the words in the sentence. Also, the same words cannot be mapped to different token/pattern. And also, different words cannot be mapped to a same token/pattern.

The following C++ uses istringstream to process a string into words/tokens. The complexity is O(N) where N is the number of the characters in the string – and O(N) space as we are using two hash maps.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        istringstream ss(str);
        string word;
        unordered_map<char, string> mapping;
        unordered_map<string, char> words;
        int i = 0;
        while (ss >> word) {
            if (i >= pattern.size()) {
                return false;
            }
            char pat = pattern[i ++];            
            if (mapping.find(pat) != mapping.end()) {
                if (word != mapping[pat]) {
                    return false;
                }
            }
            if ((words.find(word) != words.end()) && (words[word] != pat)) {
                return false;
            }
            words[word] = pat;            
            mapping[pat] = word;
        }
        return i == pattern.size();
    }
};
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        istringstream ss(str);
        string word;
        unordered_map<char, string> mapping;
        unordered_map<string, char> words;
        int i = 0;
        while (ss >> word) {
            if (i >= pattern.size()) {
                return false;
            }
            char pat = pattern[i ++];            
            if (mapping.find(pat) != mapping.end()) {
                if (word != mapping[pat]) {
                    return false;
                }
            }
            if ((words.find(word) != words.end()) && (words[word] != pat)) {
                return false;
            }
            words[word] = pat;            
            mapping[pat] = word;
        }
        return i == pattern.size();
    }
};

The following is the Python implementation of the word pattern algorithm – the code is concise but only using one dictionary/hashmap:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        arr = str.split(' ')
        if (len(arr) != len(pattern)):
            return False
        data = {}
        idx = 0
        for s in pattern:
            if not s in data:
                if arr[idx] in data.values():
                    return False
                data[s] = arr[idx]
            else:
                if data[s] != arr[idx]:
                    return False
            idx += 1
        return True
class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        arr = str.split(' ')
        if (len(arr) != len(pattern)):
            return False
        data = {}
        idx = 0
        for s in pattern:
            if not s in data:
                if arr[idx] in data.values():
                    return False
                data[s] = arr[idx]
            else:
                if data[s] != arr[idx]:
                    return False
            idx += 1
        return True

The algorithm complexity is O(N^2) as we are using in operator to check if a word exists in an array.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
Best Topics and Themes for Driving Traffic to Your Blog  Want to Start a Blog For Your Family Tree? Here’s How Anyone Can  Tips for Local Business Blogs  5 Tips to Drive Traffic to Your Blog  Ideas to Help You Set Up the Home Office of Your Dreams  Wix vs Squarespace 2020 – Things You Must Know  How to Delete N Nodes After M Nodes of a Linked List?  Bruteforce Algorithm to Find the Unique Positive Integer Whose S  Clone (Deep Copy) Binary Tree With Random Pointer using Hash Map  How to Compute Running Sum of 1d Array using std::partial_sum in 
评论列表
添加评论