Problem

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.

Examples

Example 1:

1
2
3
4

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

Example 2:

1
2
3
4

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

Example 3:

1
2
3
4

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

Solution

Method 1 - Using 2 Hash tables

This problem is similar to Isomorphic Strings. We create 2 hashtables from pattern to str and str to pattern.

Why We Need 2 Hashmaps?

Consider the string [a b b a] → [dog cat cat dog]; In this case 1 hashmap from pattern to str is enough. But suppose we have [a b b c] → [dog cat cat dog]. If we just use one hashmap, we will return true. So, important is dog should also match to a and not c.

Code

 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

public boolean wordPattern(String pattern, String str) {
	String[] words = str.split(" ");
	if (words.length != pattern.length()) {
		return false;
	}
	Map<String, Character> wordToChar = new HashMap<>();
	Map<Character, String> charToWord = new HashMap<>();

	for (int i = 0; i < words.length; i++) {
		String word = words[i];
		char c = pattern.charAt(i);
		if(!wordToChar.containsKey(word) && !charToWord.containsKey(c)){
			wordToChar.put(word, c);
			charToWord.put(c, word);
		}else if(wordToChar.containsKey(word) && charToWord.containsKey(c)){
			char d = wordToChar.get(word);
			String word2 = charToWord.get(c);
			if(d != c || !word.equals(word2)){
				return false;
			}
		}else {
			return false;
		}
	}
	return true;
}
 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

use std::collections::HashMap;

pub fn word_pattern(pattern: String, s: String) -> bool {
	if pattern.len() != s.matches(' ').count() + 1 {
		return false;
	}

	let mut p2s: HashMap<char, &str> = HashMap::new();
	let mut s2p: HashMap<&str, char> = HashMap::new();


	for (word, c) in s.split_ascii_whitespace().zip(pattern.chars()) {
		if !p2s.contains_key(&c) && !s2p.contains_key(word) {
			p2s.insert(c, word);
			s2p.insert(word, c);
		} else if p2s.contains_key(&c) && s2p.contains_key(word) {
			let word2 = p2s.get(&c).unwrap();
			let c2 = s2p.get(word).unwrap();
			if word2 != &word || c2 != &c {
				return false;
			}
		} else {
			return false;
		}
	}
	return true;
}