[LeetCode] 290. Word Pattern

轉自LeetCode

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.

Examples:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. pattern = "abba", str = "dog dog dog dog" should return false.

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

<Solution>

這題給一個 pattern，然後去看一個字串裡面的子字串，是否符合 pattern 的分佈

想法如下

• 用兩個 HashMap 分別來記錄 pattern 出現的位置，和子字串的位置

• 如果再遇到已配對過的 pattern 和子字串，其各自記錄的位置不符合的話，就回傳 false

• 如果再遇到已配對過的 pattern 和子字串，其各自記錄的位置符合的話，更新其位置

• 如果pattern 和子字串的數目，對不起來，也回傳 false

code如下

C++ (C++的 unordered_map，如果 key 不存在，直接存取的話，會直接創建，其預設int是0)

	class Solution {
	public:
	bool wordPattern(string pattern, string str) {
	unordered_map<char, int> patternMap;
	unordered_map<string, int> wordMap;
	istringstream iss(str);
	const int patternLen = pattern.length();
	int i = 0;
	for(string word; iss >> word; ++i) {
	if(i == patternLen || patternMap[pattern[i]] != wordMap[word]) {
	return false;
	}
	patternMap[pattern[i]] = wordMap[word] = i+1;
	}
	return i == patternLen;
	}
	};

view raw wordPattern.cpp hosted with ❤ by GitHub

Java
可以再簡化，因為 HashMap 可以不指定型別

	class Solution {
	public boolean wordPattern(String pattern, String str) {
	final String[] words = str.split(" ");
	if (words.length == pattern.length()) {
	HashMap map = new HashMap();
	for(int i = 0; i < words.length; ++i) {
	if (!Objects.equals(map.put(pattern.charAt(i), i), map.put(words[i], i))) {
	return false;
	}
	}
	return true;
	}
	return false;
	}
	}

view raw wordPattern.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun wordPattern(pattern: String, s: String): Boolean {
	val str = s.split(' ')
	if(pattern.length != str.size) {
	return false
	}
	val patternMap = mutableMapOf<Char,Int>()
	val strMap = mutableMapOf<String,Int>()
	for(i in str.indices) {
	when {
	patternMap[pattern[i]] == null && strMap[str[i]] == null -> {
	patternMap[pattern[i]] = i
	strMap[str[i]] = i
	}
	patternMap[pattern[i]] != null && strMap[str[i]] != null -> {
	if (patternMap[pattern[i]]!! != strMap[str[i]]!!) {
	return false
	}
	}
	else -> return false
	}
	}
	return true
	}
	}

view raw word_pattern.kt hosted with ❤ by GitHub