Leetocde_290_Word Pattern

本文是在学习中的总结，欢迎转载但请注明出处：http://blog.csdn.net/pistolove/article/details/49717803

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:

pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

思路：

（1）题意为给定一种字符样式和一个字符串，要求判断该字符串是否为给定的样式。

（2）由于给定的pattern由若干字符组成，不同的字符应该对应不同的字符串，而相同的字符应该对应相同的字符串。这样，可以通过Map对其进行实现。首先，将pattern转化为字符数组pt，将待判断的字符串转为字符串数组split；其次，如果两个数组的长度不等，则匹配失败；否则，遍历字符数组pt，如果当前字符在Map不存有，则判断待判断的字符串数组split在对应位置的值是否存于Map对应的Value中，如果存有，则匹配失败，否则，将当前位置对应的字符和字符串存入Map中；如果当前遍历的字符在Map对应的key中存有，判断key对应的value是否为空，如果不为空，则判断当前的value值和split对应的值是否相等，相等则继续，否则匹配失败；如果遍历的字符在Map对应的key中不存有，则判断value中是否存有split对应的值，如果有则匹配失败，否则将当前key和value加入Map中。

（3）详情见下方代码。希望本文对你有所帮助。

import java.util.HashMap;
import java.util.Map;

public class Word_Pattern {

	public static void main(String[] args) {
		System.err.println(wordPattern("abba", "dog dog dog dog"));
	}

	public static boolean wordPattern(String pattern, String str) {
		char[] pt = pattern.toCharArray();
		String[] split = str.split(" ");

		if (pt.length != split.length)
			return false;

		Map<Character, String> map = new HashMap<Character, String>();

		for (int i = 0; i < pt.length; i++) {
			if (!map.containsKey(pt[i])) {
				if (map.values().contains(split[i])) {
					return false;
				} else {
					map.put(pt[i], split[i]);
				}
			} else {
				if (map.get(pt[i]) != null) {
					if (map.get(pt[i]).equals(split[i])) {
						continue;
					} else {
						return false;
					}
				} else {
					if (map.values().contains(split[i])) {
						return false;
					} else {
						map.put(pt[i], split[i]);
					}
				}
			}
		}
		return true;
	}
}

巴特西

Leetocde_290_Word Pattern

最新文章

热门文章