如何更高效检查str2拆分后的所有子串是否均存在于str1中？

问题背景 #

给定两个字符串：

string str1 = "021A,775U,000A,021A,1U2,206B,240,249,255B,260,263B,280,294,2U1,306B,336B,345,427,440,442,474,477,4U4,500,508,523,543L,580,584,772,802,P55,VB";
string str2 = "772+240+802+P55+263B+1U2+VB";

需求是判断str2按+拆分后的所有子串，是否都存在于str1按,拆分后的集合中。现有实现是将str1拆分为数组，遍历str2子串逐一检查，符合条件返回true（如str2），否则返回false（如str3 = "772+240+802+P55+263B+1U2+V"）。

补充条件：

• str1最大长度约1000，拆分后的子串唯一且已排序
• str2最大长度约700（平均200），拆分后的子串唯一但未排序

优化方案 #

结合str1的特性，有三种比原实现更高效的方案：

1. 使用HashSet实现O(1)查找

利用HashSet的常数时间查找特性，替代数组的线性遍历，大幅降低总操作量。

var str1Set = new HashSet<string>(str1.Split(','));
foreach (var s in str2.Split('+'))
{
    if (!str1Set.Contains(s))
    {
        return false;
    }
}
return true;

优势：原数组遍历每次查找需O(1000)时间，HashSet只需O(1)，平均场景下总操作量从20万次降至200次，性能提升显著。

2. 利用已排序特性做二分查找

因为str1拆分后是有序数组，用Array.BinarySearch实现对数时间查找，无需额外内存开销。

string[] str1Arr = str1.Split(',');
foreach (var s in str2.Split('+'))
{
    if (Array.BinarySearch(str1Arr, s) < 0)
    {
        return false;
    }
}
return true;

优势：每次查找仅需O(log 1000)≈10次操作，总操作量约2000次，接近HashSet效率，同时节省HashSet的内存占用。

3. 预缓存str1结果（多次调用场景）

如果检查逻辑会被频繁调用，提前缓存str1的拆分集合，避免重复拆分和初始化的开销。

// 提前初始化缓存（比如类的静态字段）
private static readonly HashSet<string> Str1Cache = new HashSet<string>("021A,775U,...".Split(','));

// 检查方法
public bool CheckAllExist(string str2)
{
    foreach (var s in str2.Split('+'))
    {
        if (!Str1Cache.Contains(s))
        {
            return false;
        }
    }
    return true;
}

优势：彻底消除重复处理str1的开销，多次调用时性能最优。

方案对比 #

内容的提问来源于stack exchange，提问作者jigga