Nodejs 面试题，欢迎解答

Node.js 面试题：字符串字符存在性判断

问题描述

给定两个字符串 a 和 b，判断字符串 b 中的每一个字符是否存在于字符串 a 中。

var a = 'lkjgfaoids';
var b = 'adk';

解法一：双重循环（性能不佳）

以下是原始的双重循环解法：

var a = 'lkjgfaoids';
var b = 'adk';

var as = a.split('');
var bs = b.split('');

for (var i in as) {
    for (var k in bs) {
        if (as[i] === bs[k]) {
            console.log('Character ' + bs[k] + ' exists in string a');
        }
    }
}

问题：这种解法的时间复杂度为 O(n * m)，其中 n 是字符串 a 的长度，m 是字符串 b 的长度。这会导致性能低下，特别是在处理较长的字符串时。

解法二：使用 indexOf 方法（性能有所提升）

改进的方法是使用 String.prototype.indexOf 方法来查找字符是否存在：

var a = 'lkjgfaoids';
var b = 'adk';

var bs = b.split('');

for (var i in bs) {
    if (a.indexOf(bs[i]) !== -1) {
        console.log('Character ' + bs[i] + ' exists in string a');
    }
}

问题：虽然这种方法避免了双重循环，但 indexOf 方法仍然需要遍历整个字符串 a 来查找每个字符。因此，时间复杂度仍然是 O(n * m)。

最佳解法：使用哈希表（时间复杂度为 O(n + m)）

为了进一步提高性能，我们可以使用哈希表（对象）来存储字符串 a 中的所有字符，并通过一次遍历来检查字符串 b 中的字符是否存在于哈希表中：

var a = 'lkjgfaoids';
var b = 'adk';

// 创建一个哈希表来存储字符串 a 中的字符
var charMap = {};

// 将字符串 a 中的每个字符添加到哈希表中
for (var i = 0; i < a.length; i++) {
    charMap[a[i]] = true;
}

// 检查字符串 b 中的每个字符是否存在于哈希表中
var bs = b.split('');
for (var i = 0; i < bs.length; i++) {
    if (charMap[bs[i]]) {
        console.log('Character ' + bs[i] + ' exists in string a');
    }
}

解释：

• 使用哈希表存储字符串 a 中的字符可以将查找时间从 O(n) 降低到 O(1)。
• 时间复杂度为 O(n + m)，其中 n 是字符串 a 的长度，m 是字符串 b 的长度。
• 这种方法显著提高了性能，尤其是在处理长字符串时。

通过这种方式，我们可以在较短的时间内高效地完成字符存在性的判断。