leetcode - [290] Word Pattern

2020/06/29

问题描述

Given a pattern and a string str, find if str follows the same pattern.

判断字符串str中的单词是否具有pattern一样的模式。

举个例子:

Example 1:
Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:
Input:pattern = "abba", str = "dog cat cat fish"
Output: false

类似题目:

[242] Valid Anagram
[205] Isomorphic Strings

解法1

Thanks @lc_cl_aaa

梳理下思路:

首先,我们需要借助一个HashMap与一个HashSet

其实,就使用一个HashMap也可以搞定,但是时间复杂度会上升到O(n^2)

因为HashMap.containsValue()方法的时间复杂度为O(n)

然后,判断map中是否存在pattern中的对应的字母。

若存在,则判断当前字符串arr[i]是否与map中保存的一致。

若不存在,则判断当前字符串arr[i]是否能加入set中。

如果不能加入,则表示该字符串已经匹配了另一个字母。

来看下实现:

class Solution {
    public boolean wordPattern(String pattern, String str) {
        
        int        len = pattern.length();
        String[]   arr = str.split("\\s");
        HashMap<Character, String> map = new HashMap<>();
        HashSet<String> set = new HashSet<>();
        if (len != arr.length) return false;
        
        for (int i = 0; i < len; i++){
            char   cur = pattern.charAt(i);
            String s   = arr[i];
            if (map.containsKey(cur)){
                if (!map.get(cur).equals(s)) return false;
            } else {
                if (!set.add(s)) return false;
                map.put(cur, s);
            }
        }
        return true;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory