字符串匹配 - 字符串条件匹配 - 《学习笔记》

2047. 句子中的有效单词数

句子仅由小写字母（'a' 到 'z'）、数字（'0' 到 '9'）、连字符（'-'）、标点符号（'!'、'.' 和 ','）以及空格（' '）组成。每个句子可以根据空格分解成 一个或者多个 token ，这些 token 之间由一个或者多个空格 ' ' 分隔。
如果一个 token 同时满足下述条件，则认为这个 token 是一个有效单词：

仅由小写字母、连字符和/或标点（不含数字）。
至多一个 连字符 '-' 。如果存在，连字符两侧应当都存在小写字母（"a-b" 是一个有效单词，但 "-ab" 和 "ab-" 不是有效单词）。
至多一个 标点符号。如果存在，标点符号应当位于 token 的末尾。

这里给出几个有效单词的例子："a-b."、"afad"、"ba-c"、"a!" 和 "!" 。
给你一个字符串 sentence ，请你找出并返回 sentence 中 有效单词的数目 。

示例 1：
输入：sentence = “cat and dog“
输出：3
解释：句子中的有效单词是 “cat”、”and” 和 “dog”

示例 2：
输入：sentence = “!this 1-s b8d!”
输出：0
解释：句子中没有有效单词
“!this” 不是有效单词，因为它以一个标点开头
“1-s” 和 “b8d” 也不是有效单词，因为它们都包含数字

示例 3：
输入：sentence = “alice and bob are playing stone-game10”
输出：5
解释：句子中的有效单词是 “alice”、”and”、”bob”、”are” 和 “playing”
“stone-game10” 不是有效单词，因为它含有数字

示例 4：
输入：sentence = “he bought 2 pencils, 3 erasers, and 1 pencil-sharpener.“
输出：6
解释：句子中的有效单词是 “he”、”bought”、”pencils,”、”erasers,”、”and” 和 “pencil-sharpener.”

提示：

1 <= sentence.length <= 1000
sentence 由小写英文字母、数字（0-9）、以及字符（' '、'-'、'!'、'.' 和 ','）组成
句子中至少有 1 个 token

思路：
直接用Java中的正则表达式Java正则

import java.util.regex.*;
class Solution {
    public int countValidWords(String sentence) {
        String[] ss = sentence.trim().split("\\s+");
        int cnt = 0;
        Pattern p = Pattern.compile("^[a-z]*([a-z]-[a-z]+)?[!.,]?$");
        for (String s : ss) {
            if (p.matcher(s).matches())
                cnt++;
        }
        return cnt;
    }
}

注意这里用的不是String.matches()方法（每次匹配都会创建一个正则模式，效率低），而是用一个模式多次匹配以提高效率！

class Solution {
    public int countValidWords(String ssss) {
        String[] ss = ssss.split(" ");
        // System.out.println(Arrays.toString(ss));
        int cnt = 0;
        for (String s : ss) {
            int n = s.length();
            int c1 = 0, c2 = 0, c3 = 0, c4 = 0;
            for (int i = 0; i < n; i++) {
                char ch = s.charAt(i);
                if (ch >= 'a' && i <= 'z')
                    c1++;
                else if (ch == '-') {
                    c2++;
                    if (i > 0 && i < n - 1) {
                        if (!(s.charAt(i - 1) >= 'a' && s.charAt(i - 1) <= 'z'))
                            c2 = 2;
                        if (!(s.charAt(i + 1) >= 'a' && s.charAt(i + 1) <= 'z'))
                            c2 = 2;
                    }
                }
                else if (ch >= '0' && ch <= '9')
                    c3++;
                else
                    c4++;
            }
            // System.out.println(c1 + " " + c2 + " " + c3 + " " + c4);
            if (c1 == 0 && c4 == 0)
                continue;
            if (c3 > 0)
                continue;
            if (c2 > 1)
                continue;
            if (c2 == 1 && (s.charAt(0) == '-' || s.charAt(n - 1) == '-'))
                continue;
            if (c4 > 1)
                continue;
            if (c4 == 1 && c1 > 0 && s.charAt(n - 1) >= 'a' && s.charAt(n - 1) <= 'z')
                continue;
            // System.out.println(s + "==");
            cnt++;
        }
        return cnt;
    }
}

676. 实现一个魔法字典

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
实现 MagicDictionary 类：

MagicDictionary() 初始化对象
void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中一个字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

示例：
输入 [“MagicDictionary”, “buildDict”, “search”, “search”, “search”, “search”] [[], [[“hello”, “leetcode”]], [“hello”], [“hhllo”], [“hell”], [“leetcoded”]] 输出 [null, null, false, true, false, false] 解释 MagicDictionary magicDictionary = new MagicDictionary(); magicDictionary.buildDict([“hello”, “leetcode”]); magicDictionary.search(“hello”); // 返回 False magicDictionary.search(“hhllo”); // 将第二个 ‘h’ 替换为 ‘e’ 可以匹配 “hello” ，所以返回 True magicDictionary.search(“hell”); // 返回 False magicDictionary.search(“leetcoded”); // 返回 False

提示：

1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写英文字母组成
dictionary 中的所有字符串 互不相同
1 <= searchWord.length <= 100
searchWord 仅由小写英文字母组成
buildDict 仅在 search 之前调用一次
最多调用 100 次 search

思路：
方法1：暴力，讲单词列表中的单词按长度分组，在与给定单词长度相等的分组中找目标单词是否存在，具体做法是遍历一遍统计不同元素的个数，超过1直接break，等于1返回true，否则继续遍历单词列表中的下一个，若都不行，返回false。
方法2：字典树，搜索时加点东西就行了
方法3：广义邻居，用哈希表统计每个单词的所有广义邻居，并且不同单词的相同广义邻居需要进行累加

//字典树
class Trie {
    class TrieNode {
        TrieNode[] son = new TrieNode[26];
        int cnt;
    }
    TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.son[idx] != null)
                cur = cur.son[idx];
            else {
                cur.son[idx] = new TrieNode();
                cur = cur.son[idx];
            }
        }
        cur.cnt++;
    }
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.son[idx] == null)
                return false;
            cur = cur.son[idx];
        }
        return cur.cnt > 0;
    }
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.son[idx] == null)
                return false;
            cur = cur.son[idx];
        }
        return true;
    }
}
/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

// 广义邻居
class MagicDictionary {
    Set<String> set = new HashSet<>();
    Map<String, Integer> map = new HashMap<>();
    public MagicDictionary() {
    }
    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            set.add(s);
            for (int i = 0; i < s.length(); i++) {
                String t = s.substring(0, i) + "." + s.substring(i + 1, s.length());
                map.merge(t, 1, Integer::sum);
            }
        }
    }
    public boolean search(String searchWord) {
        for (int i = 0; i < searchWord.length(); i++) {
            String t = searchWord.substring(0, i) + "." + searchWord.substring(i + 1, searchWord.length());
            int size = map.getOrDefault(t, 0);
            if (size > 1) return true;
            if (size == 1 && !set.contains(searchWord)) return true;
        }
        return false;
    }
}
/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */

820. 单词的压缩编码

单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

words.length == indices.length
助记字符串 s 以 ‘#’ 字符结尾
对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 ‘#’ 字符结束（但不包括 ‘#’）的 子字符串 恰好与 words[i] 相等

给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度。

示例 1：
输入：words = [“time”, “me”, “bell”] 输出：10 解释：一组有效编码为 s = “time#bell#” 和 indices = [0, 2, 5] 。 words[0] = “time” ，s 开始于 indices[0] = 0 到下一个 ‘#’ 结束的子字符串，如加粗部分所示 “time#bell#” words[1] = “me” ，s 开始于 indices[1] = 2 到下一个 ‘#’ 结束的子字符串，如加粗部分所示 “time#bell#” words[2] = “bell” ，s 开始于 indices[2] = 5 到下一个 ‘#’ 结束的子字符串，如加粗部分所示 “time#bell#”
示例 2：
输入：words = [“t”] 输出：2 解释：一组有效编码为 s = “t#” 和 indices = [0] 。

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i] 仅由小写字母组成

思路：
方法1：暴力，将所有字符串加入集合中，枚举每个字符串的所有后缀，如何集合中包含该后缀，将其从集合中删去。
集合中剩余字符串的字符数+字符串个数就是最终的答案。
方法2：字典树，将所有字符串倒着插入字典树中，只需统计所有叶节点的深度+所有叶节点的个数即可。
也就是说我们需要标记一下一个节点是否为叶节点。使用cnt来表示，若cnt = 1表示该节点不是叶节点，若为0表示该节点是叶节点。
同时在构造字典树时返回插入每个字符串时的最后一个TrieNode节点，用来方便访问所有叶节点。

//方法1
class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> set = new HashSet<>(Arrays.asList(words));
        for (String s : words) {
            for (int i = 1; i < s.length(); i++) {
                set.remove(s.substring(i));
            }
        }
        int cnt = 0;
        for (String s : set) {
            cnt += s.length() + 1;
        }
        return cnt;
    }
}

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Map<Trie.TrieNode, String> map = new HashMap<>();
        Trie trie = new Trie();
        for (String s : words) {
            Trie.TrieNode t = trie.insert(s);
            map.put(t, s);
        }
        int res = 0;
        for (Trie.TrieNode cur : map.keySet()) {
            if (cur.cnt == 0)
                res += map.get(cur).length() + 1;
        }
        return res;
    }
}
class Trie {
    class TrieNode {
        TrieNode[] son = new TrieNode[26];
        int cnt;
    }
    TrieNode root = new TrieNode();
    TrieNode insert(String s) {
        TrieNode cur = root;
        for (int i = s.length() - 1; i >= 0; i--) {
            int idx = s.charAt(i) - 'a';
            if (cur.son[idx] == null) {
                cur.cnt++;
                cur.son[idx] = new TrieNode();
            }
            cur = cur.son[idx];
        }
        return cur;
    }
}