当前位置：首页 > article >正文

算法随打：拼写单词

article 2025/3/17 13:36:47

问题描述

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

示例 1：
输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
示例 2：
输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。
提示：

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都仅包含小写英文字母

思路一

1.number用于累计可以被chars完全删除的单词的总长度。index用于存储当前处理的单词的长度。

2.使用外层循环遍历words数组中的每个单词。在处理每个单词之前，先将该单词的长度存储在index变量中。内层循环遍历chars字符串中的每个字符。使用replaceFirst方法尝试删除words[i]中出现的chars.charAt(j)字符的第一个匹配项。

3.如果经过替换操作后，words[i]变为空字符串，则表示该单词可以完全被chars中的字符组合删除。在这种情况下，将原始单词的长度（存储在index中）加到number上，并跳出内层循环。方法最终返回所有能被chars中字符完全删除的单词的长度之和。

代码展示

public static int countCharacters(String[] words, String chars) {
        int number=0;
        int index;
        for(int i=0;i<words.length;i++){
            index=words[i].length();//记录本次字符串的长度。
            for(int j=0;j<chars.length();j++){
                words[i] = words[i].replaceFirst(String.valueOf(chars.charAt(j)), "");
                if(words[i].isEmpty()){//如果字符串全部成功替换，则记录下来。
                    number=number+index;
                    break;//结束内层循环。
                }
            }
        }
        return number;
    }
}

缺点：时间复杂度和空间复杂度出奇的高。能通过也是奇迹。