algorithms►leetcode

029-判断子序列

392. 判断子序列-Easy

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

题解1： 执行用时击败100% （indexOf() 用法复习）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    const sLen = s.length;
    const tLen = t.length;
    let prevIndex = -1;
    let matchedCount =0;

    for (let i = 0; i < sLen; i++) {
        // 从prevIndex+1开始查找当前字符
        const currentIndex = t.indexOf(s[i], prevIndex + 1);
        if (currentIndex !== -1) { //indexOf查不到的情况下返回-1
            prevIndex = currentIndex;
            matchedCount++;
        } else {
            // 如果没找到直接终止
            return false;
        }
    }
    return matchedCount === sLen;
};

题解2：简洁，通用

1
2
3
4
5
6
7
8
var isSubsequence = function(s, t) {
    let i=0,j=0;
    while(i<s.length && j<t.length) {
        if(s[i] === t[j]) i++;
        j++;
    }
    return i===s.length;
};

进阶：针对海量输入的 S 检查是否为 T 的子序列的优化方案

当需要处理 10亿级 的字符串 S1, S2, ..., Sk 并判断它们是否为 T 的子序列时，直接对每个 S 使用双指针法（O(n) 时间复杂度）会导致总时间复杂度达到 **O(k·n)**，这在 k=10^9 时显然不可行。以下是分阶段的优化策略：

1. 预处理阶段：对 T 建立索引

目标

将 T 转换为一种支持 快速查询字符位置 的数据结构，避免每次处理 S 时都重新扫描 T。

方法：建立字符位置映射表

  • 使用哈希表记录 T 中每个字符的 所有出现位置（按顺序存储）。
  • 例如 T = "ahbgdc" 的映射表：
    1
    2
    3
    4
    5
    6
    7
    8
    {
      'a': [0],
      'h': [1],
      'b': [2],
      'g': [3],
      'd': [4],
      'c': [5]
    }

代码实现

1
2
3
4
5
6
7
8
9
10
11
function buildIndex(T) {
    const index = {};
    for (let i = 0; i < T.length; i++) {
        const char = T[i];
        if (!index[char]) index[char] = [];
        index[char].push(i);
    }
    return index;
}

const indexT = buildIndex(T); // 预处理 T

复杂度分析

  • 时间复杂度：O(n)（仅需一次）
  • 空间复杂度：O(n)

2. 查询阶段：对每个 S 进行高效匹配

目标

利用预处理好的 indexT，快速判断 S 是否为 T 的子序列。

方法：二分查找下一个匹配位置

  1. 初始化 currentPos = -1（表示从 T 的开头开始匹配）。
  2. 对于 S 中的每个字符 c：
    • 如果 c 不在 indexT 中，直接返回 false。
    • 在 indexT[c] 中 二分查找 第一个大于 currentPos 的位置。
    • 如果找到，更新 currentPos；否则返回 false。

复杂度分析（单次查询）

  • 时间复杂度：O(m log L)
    • m 是 S 的长度，L 是字符在 T 中的平均出现次数。
    • 例如 T="aaaabbbb"，L=4。
  • 空间复杂度：O(1)

实现示例（完整代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 预处理阶段
const indexT = {};
for (let i = 0; i < T.length; i++) {
    const char = T[i];
    if (!indexT[char]) indexT[char] = [];
    indexT[char].push(i);
}

// 查询阶段（处理海量 S）
function batchCheck(SList, indexT) {
    return SList.map(S => {
        let currentPos = -1;
        for (const c of S) {
            const positions = indexT[c];
            if (!positions) return false;
            // 二分查找
            let left = 0, right = positions.length;
            while (left < right) {
                const mid = Math.floor((left + right) / 2);
                if (positions[mid] > currentPos) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            if (left === positions.length) return false;
            currentPos = positions[left];
        }
        return true;
    });
}

// 示例使用
const SList = ["abc", "axc", "ahc"];
const results = batchCheck(SList, indexT);
console.log(results); // [true, false, true]

3. 总复杂度对比

方法 预处理时间 单次查询时间 总时间（k=10^9）
原始双指针法 无 O(n) O(10^9 · n) → 不可行
预处理+二分查找 O(n) O(m log L) O(n + 10^9 · m log L)

4. 进一步优化（针对特定场景）

(1) 如果 T 很短（如 n < 1000）

  • 直接使用双指针法，避免预处理开销。

(2) 如果 S 的平均长度远小于 T（如 m << n）

  • 预处理 T 的收益可能不明显，需测试权衡。

(3) 并行化处理

并行化处理海量字符串检查
1. 预处理阶段（单机）
  • 构建字符位置索引：对 T 建立哈希表，记录每个字符的所有出现位置（有序数组）。
2. 查询阶段（分布式并行）
方案一：多线程（Node.js Worker Threads）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const { Worker, isMainThread, parentPort, workerData } = require('worker_threads');

// 主线程逻辑
if (isMainThread) {
    const indexT = buildIndex(T);
    const SList = [...]; // 海量 S 列表
    const chunkSize = Math.ceil(SList.length / 4); // 分4个线程
    const workers = [];

    for (let i = 0; i < 4; i++) {
        const chunk = SList.slice(i * chunkSize, (i + 1) * chunkSize);
        workers.push(new Worker(__filename, {
            workerData: { indexT, chunk }
        }));
    }

    // 收集结果
    workers.forEach(worker => {
        worker.on('message', (results) => {
            console.log(results);
        });
    });
}
// 子线程逻辑
else {
    const { indexT, chunk } = workerData;
    const results = chunk.map(S => isSubsequence(S, indexT));
    parentPort.postMessage(results);
}

function isSubsequence(S, indexT) {
    let currentPos = -1;
    for (const c of S) {
        const positions = indexT[c];
        if (!positions) return false;
        // 二分查找第一个大于 currentPos 的位置
        const idx = binarySearch(positions, currentPos);
        if (idx === -1) return false;
        currentPos = positions[idx];
    }
    return true;
}
方案二：MapReduce（大规模分布式, 离线计算）/ Spark(离线/实时计算/流处理/图计算/机器学习…)
  1. Map 阶段：
    • 将海量 S 分片到多台机器。
    • 每台机器读取 T 的索引（可共享存储如 Redis）。
  2. Reduce 阶段：
    • 汇总各机器的结果。
3. 优化点
  • 索引共享：将 T 的索引存储在分布式缓存（如 Redis）中，避免重复构建。
  • 动态负载均衡：根据机器性能动态分配 S 的分片大小。

三、复杂度对比

方法 预处理时间 单次查询时间 总时间（k=10^9, p=1000台机器）
单机双指针 无 O(n) O(10^9 · n) → 不可行
预处理+并行查询 O(n) O(m log L) O(n + (10^9 · m log L)/p)

四、关键问题解答

并行化如何保证正确性？
  • 只读操作：各线程/机器独立处理不同的 S，无需共享可变状态。
  • 索引一致性：预处理后的 T 索引是只读的，可安全共享。
如何处理超长 T 或 S？
  • 压缩索引：对 T 的字符位置使用差值编码（如存储相邻位置的差值）。
  • 分批加载：将 S 分批次处理，避免内存溢出。

***总结***

  • 单机优化：预处理 T 为字符位置索引，将单次查询时间从 O(n) 降至 O(m log L)。
  • 并行化：通过多线程或分布式框架（如 MapReduce）横向扩展，处理海量 S。
  • 适用场景：T 较长且稳定，S 数量极大（如日志分析、DNA序列匹配）。

6. 边界情况处理

情况 处理方式
T 为空字符串 所有 S 若非空则返回 false
S 为空字符串 直接返回 true
T 或 S 含 Unicode 字符 需确保哈希表支持 Unicode

总结

  • **预处理 T**：建立字符位置索引表（O(n) 时间）。
  • 高效查询：对每个 S 使用二分查找（O(m log L) 时间）。
  • 适用场景：k 极大（如 10^9）、T 较长且 S 长度适中。
  • 权衡点：若 T 极短或 S 极长，可能需要调整策略。
algorithms►leetcode

030-最长公共前缀

14.最长公共前缀问题-Easy

问题描述

给定一个字符串数组 strs，找出所有字符串的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例

1
2
3
4
5
输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""

方法一：水平扫描法（逐字符比较）

核心思想

  1. 以第一个字符串为基准。
  2. 逐个字符与其他字符串的对应位置比较。
  3. 遇到不匹配时停止，返回当前匹配的前缀。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    
    let prefix = strs[0]; // 初始化为第一个字符串
    
    for (let i = 1; i < strs.length; i++) {
        //用startsWith更直观： !strs[i].startsWith(prefix)
        while (strs[i].indexOf(prefix) !== 0) { // 检查当前字符串是否以prefix开头
            prefix = prefix.slice(0, prefix.length - 1); // 缩短prefix
            if (prefix === "") return ""; // 提前终止
        }
    }
    
    return prefix;
};

复杂度分析

  • 时间复杂度：O(S)，其中 S 是所有字符串的字符总数。
  • 空间复杂度：O(1)。

方法二：垂直扫描法（逐列比较）

核心思想

  1. 按列比较所有字符串的相同位置字符。
  2. 遇到不匹配时停止。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    
    for (let i = 0; i < strs[0].length; i++) {
        const char = strs[0][i]; // 当前列的基准字符
        for (let j = 1; j < strs.length; j++) {
            if (i === strs[j].length || strs[j][i] !== char) {
                return strs[0].slice(0, i); // 返回当前匹配的前缀
            }
        }
    }
    
    return strs[0]; // 全部字符匹配
};

复杂度分析

  • 时间复杂度：O(S)，最坏情况下需要比较所有字符。
  • 空间复杂度：O(1)。

方法三：分治法

核心思想

  1. 将问题分解为子问题：分别求左半部分和右半部分的最长公共前缀。
  2. 合并子问题的解。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    return divideAndConquer(strs, 0, strs.length - 1);
};

function divideAndConquer(strs, left, right) {
    if (left === right) return strs[left];
    
    const mid = Math.floor((left + right) / 2);
    const leftPrefix = divideAndConquer(strs, left, mid);
    const rightPrefix = divideAndConquer(strs, mid + 1, right);
    
    return commonPrefix(leftPrefix, rightPrefix);
}

function commonPrefix(str1, str2) {
    const minLen = Math.min(str1.length, str2.length);
    for (let i = 0; i < minLen; i++) {
        if (str1[i] !== str2[i]) {
            return str1.slice(0, i);
        }
    }
    return str1.slice(0, minLen);
}

复杂度分析

  • 时间复杂度：O(S)，其中 S 是所有字符串的字符总数。
  • 空间复杂度：O(m log n)，递归调用栈的深度。

方法四：二分查找法

核心思想

  1. 对最短字符串的长度进行二分查找。
  2. 检查当前长度是否是所有字符串的公共前缀。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    
    let minLen = Math.min(...strs.map(s => s.length));
    let low = 1, high = minLen;
    
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (isCommonPrefix(strs, mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return strs[0].slice(0, (low + high) / 2);
};

function isCommonPrefix(strs, len) {
    const prefix = strs[0].slice(0, len);
    for (let i = 1; i < strs.length; i++) {
        if (!strs[i].startsWith(prefix)) {
            return false;
        }
    }
    return true;
}

复杂度分析

  • 时间复杂度：O(S log m)，其中 m 是最短字符串的长度。
  • 空间复杂度：O(1)。

方法对比

方法 时间复杂度 空间复杂度 适用场景
水平扫描 O(S) O(1) 通用
垂直扫描 O(S) O(1) 字符较短时
分治法 O(S) O(m log n) 大规模数据
二分查找 O(S log m) O(1) 字符串较长时

边界情况处理

  1. 空数组：直接返回 ""。
  2. 单字符串：返回该字符串本身。
  3. 完全匹配：返回最短字符串。

总结

  • 推荐方法：垂直扫描法（代码简洁，效率高）。
  • 优化选择：如果字符串非常长，考虑二分查找法。
  • 分治法的优势：适合分布式计算或超大规模数据。