Given apatternand a stringstr, find ifstrfollows the same pattern.

Here follow means a full match, such that there is a bijection between a letter inpatternand a non-empty word instr.

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 assumepatterncontains only lowercase letters, andstrcontains lowercase letters separated by a single space.

Solution: pattern每种字母对应不同的单词。用hashmap记录对应关系,hashset记录已经出现过的单词

    public boolean wordPattern(String pattern, String str) {
        if (pattern == null || str == null || str.length() == 0) {
            return false;
        }
        HashMap<Character, String> hashmap = new HashMap<>();
        HashSet<String> hashset = new HashSet<>();
        int j = 0, i = 0;
        for (; i < pattern.length() && j < str.length(); i++) {
            char c = pattern.charAt(i);
            int k = j;
            while(k < str.length() && str.charAt(k) != ' ') {
                k++;
            }
            String substring = str.substring(j, k);
            j = k + 1;
            if (hashmap.containsKey(c)) {
                if (!hashmap.get(c).equals(substring)) {
                    return false;
                }
            } else {
                //看这单词是否已有字母对应
                if (hashset.contains(substring)) {
                    return false;
                }
                hashmap.put(c, substring);
                hashset.add(substring);
            }
        }
        //要到末尾,避免有多余的字母或单词
        return j == str.length() + 1 && i == pattern.length();
    }

results matching ""

    No results matching ""