Leetocde_290_Word Pattern

时间:2021-10-28 05:55:50

本文是在学习中的总结,欢迎转载但请注明出处: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:

  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.

思路:

(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;
	}
}