本文旨在提供一种高效的方法，用于在 NodeJS 中判断一个字符串是否包含长度大于 3 的英文单词。通过构建预处理的字典 HashMap，并结合字符串迭代查找，可以在时间和空间复杂度之间取得较好的平衡，避免遍历庞大的字典，从而优化性能。
在 NodeJS 中，判断一个字符串是否包含英文单词，尤其是当需要在 lambda 函数中执行时，效率至关重要。直接遍历字典进行查找，效率较低。本文介绍一种更高效的方法，通过预处理字典并结合字符串迭代，来优化这一过程。
构建预处理的字典 HashMap
首先，我们需要构建一个预处理的字典 HashMap。这个过程只需要执行一次，因此可以接受较高的初始化成本。HashMap 的结构如下：
// JavaScript 中对象类似于 HashMap
const dictionaryMap = {
'hom': 'e',
'cat': '',
'bot': 'tle',
'gla': ['ss', 'cier'], // 包含 'glass' 和 'glacier'
};其中，Key 是单词的前三个字母，Value 可能是剩余的字母（如果单词长度大于 3），或者是一个数组，包含多个可能的后缀。构建这个 HashMap 的时间复杂度是 O(m)，其中 m 是字典中单词的数量。
迭代字符串并查找单词
接下来，我们迭代输入的字符串，并在 HashMap 中查找匹配的单词。
function containsEnglishWord(str, dictionaryMap) {
const n = str.length;
for (let i = 0; i < n - 2; i++) {
const lookupStr = str.substring(i, i + 3); // 获取字符串的前三个字符
if (dictionaryMap.hasOwnProperty(lookupStr)) {
const suffix = dictionaryMap[lookupStr];
if (typeof suffix === 'string') {
// 如果是字符串，直接拼接并判断
const potentialWord = lookupStr + suffix;
if (str.includes(potentialWord)) {
return true;
}
} else if (Array.isArray(suffix)) {
// 如果是数组，遍历数组，拼接并判断
for (const s of suffix) {
const potentialWord = lookupStr + s;
if (str.includes(potentialWord)) {
return true;
}
}
} else if (suffix === '') {
//如果为空字符串，说明字符串本身就是单词
return true;
}
}
}
return false;
}这段代码的时间复杂度是 O(n)，其中 n 是字符串的长度。每次查找 HashMap 的时间复杂度是 O(1)。
示例
const dictionaryMap = {
'hom': 'e',
'cat': '',
'bot': 'tle',
'gla': ['ss', 'cier'],
};
const str1 = "y89nsdadhomea98qwoi";
const str2 = ":_5678aSD.bottleads.";
const str3 = "yfugdnuagybdasglassesmidwqihhniwqnhi";
const str4 = "y89nsdadhasa98qwoi";
const str5 = ":_5678aSD.b0TTle4ds.";
const str6 = "yfugdnuagybdasmidwqihhniwqnhi";
console.log(containsEnglishWord(str1, dictionaryMap)); // true
console.log(containsEnglishWord(str2, dictionaryMap)); // true
console.log(containsEnglishWord(str3, dictionaryMap)); // true
console.log(containsEnglishWord(str4, dictionaryMap)); // false
console.log(containsEnglishWord(str5, dictionaryMap)); // false
console.log(containsEnglishWord(str6, dictionaryMap)); // false进一步优化 (可选)
- 动态规划或记忆化搜索: 如果需要查找精确的单词，可以结合动态规划或记忆化搜索，构建一棵树状结构，以便更高效地查找。
- 正则表达式: 可以使用正则表达式来匹配单词，但需要注意正则表达式的性能。
- 使用更高效的数据结构: 例如，使用 Trie 树来存储字典，可以进一步提高查找效率。
总结
通过预处理字典并构建 HashMap，可以显著提高在 NodeJS 中判断字符串是否包含英文单词的效率。这种方法的时间复杂度是 O(m) + O(n)，其中 m 是字典中单词的数量，n 是字符串的长度。空间复杂度是 O(m)，用于存储 HashMap。在实际应用中，可以根据具体的需求选择合适的优化策略。
