Description

Given a pattern and a string s, find if s 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 s.

Example 1:

1Input: pattern = "abba", s = "dog cat cat dog"
2Output: true

Example 2:

1Input: pattern = "abba", s = "dog cat cat fish"
2Output: false

Example 3:

1Input: pattern = "aaaa", s = "dog cat cat dog"
2Output: false

Constraints:

  • 1 <= pattern.length <= 300
  • pattern contains only lower-case English letters.
  • 1 <= s.length <= 3000
  • s contains only lowercase English letters and spaces ' '.
  • s does not contain any leading or trailing spaces.
  • All the words in s are separated by a single space.

Solution

This problem requires us to map characters of pattern string to words of string s. As long as both have exact same pattern, they are said to be following same pattern.

First thing, if the pattern length is not equal to s.split(' ') length then both strings are not following same pattern. If both are same length then we need to check each character maps to specific word all the time. In order to do that, we have to create a map from Character to String. This could be done even using an array.

We also have to check from String s to pattern mapping because otherwise inputs like s=abba and pattern='dog dog dog dog' will wrongly return true.

 1class Solution {
 2    private static final int MAX_SIZE = 26;
 3    public boolean wordPattern (String pattern, String s) {
 4        String[] words = s.split(" ");
 5        if (words.length != pattern.length()) {
 6            return false;
 7        }
 8
 9        String[] patternToWord = new String[MAX_SIZE];
10        Map<String, Character> wordToPattern = new HashMap<>();
11        for (int i = 0; i < pattern.length(); i++) {
12            char patternChar = pattern.charAt(i);
13            String word = words[i];
14            if (patternToWord[patternChar - 'a'] == null && !wordToPattern.containsKey(word)) {
15                patternToWord[patternChar - 'a'] = word;
16                wordToPattern.put(word, patternChar);
17            } else if (patternToWord[patternChar - 'a'] == null && wordToPattern.containsKey(word)) {
18                return false;
19            } else if (!patternToWord[patternChar - 'a'].equals(word) || wordToPattern.get(word) != patternChar) {
20                return false;
21            }
22        }
23        return true;
24    }
25}
  • Time Complexity : O(n)
  • Space Complexity: O(n)