题目描述(中等难度)

设计一个数据结构,实现 add 方法添加字符串,search 查找字符串,所查找的字符串可能含有 . ,代表任意的字符。

解法一 暴力

来个暴力的方法,用 HashSet 存入所有的字符串。当查找字符串的时候,我们首先判断 set 中是否存在,如果存在的话直接返回 true 。不存在的话,因为要查找的字符串中可能含有 . ,接下来我们需要遍历 set ,一个一个的进行匹配。

class WordDictionary {
    HashSet<String> set;

    /** Initialize your data structure here. */
    public WordDictionary() {
        set = new HashSet<>();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        set.add(word);
    }

    /**
     * Returns if the word is in the data structure. A word could contain the
     * dot character '.' to represent any one letter.
     */
    public boolean search(String word) {
        if (set.contains(word)) {
            return true;
        }
        for (String s : set) {
            if (equal(s, word)) {
                return true;
            }
        }
        return false;
    }

    private boolean equal(String s, String word) {
        char[] c1 = s.toCharArray();
        char[] c2 = word.toCharArray();
        int n1 = s.length();
        int n2 = word.length();
        if (n1 != n2) {
            return false;
        }
        for (int i = 0; i < n1; i++) {
            //. 代表任意字符,跳过
            if (c1[i] != c2[i] && c2[i] != '.') {
                return false;
            }
        }
        return true;
    }
}

当然,由于有些暴力,出现了超时。

至于优化的话,我们不要将加入的字符串一股脑的放入一个 set 中,可以通过长度进行分类,将长度相同的放到一个 set 中。这样一个一个匹配的时候,规模会减小一些。

class WordDictionary {
    HashMap<Integer,HashSet<String>> map;

    /** Initialize your data structure here. */
    public WordDictionary() {
        map = new HashMap<>();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        int n = word.length();
        //将字符串加入对应长度的 set 中
        if (map.containsKey(n)) {
            HashSet<String> set = map.get(n);
            set.add(word);
        } else {
            HashSet<String> set = new HashSet<String>();
            set.add(word);
            map.put(n, set);
        }
    }

    /**
     * Returns if the word is in the data structure. A word could contain the
     * dot character '.' to represent any one letter.
     */
    public boolean search(String word) {
        HashSet<String> set = map.getOrDefault(word.length(), new HashSet<String>());
        if (set.contains(word)) {
            return true;
        }
        for (String s : set) {
            if (equal(s, word)) {
                return true;
            }
        }
        return false;
    }

    private boolean equal(String s, String word) {
        char[] c1 = s.toCharArray();
        char[] c2 = word.toCharArray();
        int n1 = s.length();
        int n2 = word.length();
        if (n1 != n2) {
            return false;
        }
        for (int i = 0; i < n1; i++) {
            if (c1[i] != c2[i] && c2[i] != '.') {
                return false;
            }
        }
        return true;
    }
}

虽然上边的解法在 leetcode 中 AC 了,但其实很大程度上取决于 test cases 中所有字符串长度的分布,如果字符串长度全部集中于某个值,上边的解法的优化其实是无能为力的。

上边是按长度分类进行添加的,同样的我们还可以按照字符串的开头字母进行分类。当然,算法的速度同样也依赖于数据的分布,适用于数据分布均匀的情况。

解法二 前缀树

前几天在 208 题 刚做了前缀树,这里的话我们也可以通过前缀树进行存储,这样查找字符串就不用依赖于字符串的数量了。

代码的话在前缀树的基础上改一下就可以,大家可以先看一下 208 题。对于字符串中的 . ,我们通过递归去查找。

class WordDictionary {
    class TrieNode {
        TrieNode[] children;
        boolean flag;

        public TrieNode() {
            children = new TrieNode[26];
            flag = false;
            for (int i = 0; i < 26; i++) {
                children[i] = null;
            }
        }

    }
    TrieNode root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            // 当前孩子是否存在
            if (cur.children[array[i] - 'a'] == null) {
                cur.children[array[i] - 'a'] = new TrieNode();
            }
            cur = cur.children[array[i] - 'a'];
        }
        // 当前节点代表结束
        cur.flag = true;
    }

    /**
     * Returns if the word is in the data structure. A word could contain the
     * dot character '.' to represent any one letter.
     */
    public boolean search(String word) {
        return searchHelp(word, root);
    }

    private boolean searchHelp(String word, TrieNode root) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            // 对于 . , 递归的判断所有不为空的孩子
            if(array[i] == '.'){
                for(int j = 0;j < 26; j++){
                    if(cur.children[j] != null){
                        if(searchHelp(word.substring(i + 1),cur.children[j])){
                            return true;
                        }
                    }
                }
                return false;
            }
            // 不含有当前节点
            if (cur.children[array[i] - 'a'] == null) {
                return false;
            }
            cur = cur.children[array[i] - 'a'];
        }
        // 当前节点是否为是某个单词的结束
        return cur.flag;
    }
}

解法三

再分享一个 leetcode 上边的大神 @StefanPochmann 的一个想法,直接利用正则表达式。

我就不细讲了,直接看代码吧,很简洁。

import re
class WordDictionary:

    def __init__(self):
        self.words = '#'

    def addWord(self, word):
        self.words += word + '#'

    def search(self, word):
        return bool(re.search('#' + word + '#', self.words))

我用 java 改写了一下。

import java.util.regex.*;
class WordDictionary {
    StringBuilder sb;
    public WordDictionary() {
        sb = new StringBuilder();
        sb.append('#');
    }
    public void addWord(String word) {
        sb.append(word);
        sb.append('#');
    }

    public boolean search(String word) {
        Pattern p = Pattern.compile('#' + word + '#');
        Matcher m = p.matcher(sb.toString());
        return m.find();
    }
}

不过遗憾的是,javaleetcode 上这个解法会超时,python 没什么问题。当然优化的话,我们可以再像解法一那样对字符串进行分类,这里就不再写了。

上边的解法的关键就是,用 # 分割不同单词,以及查找的时候查找 # + word + # ,很妙。

解法一是直觉上的解法,分类的思想也经常用到。解法二的话,需要数据结构的积累,刚好前几题实现了前缀树,空间换时间,这里也就直接想到了。解法三的话,大概只有大神能想到了,一种完全不同的视角,很棒。

results matching ""

    No results matching ""