C++中查找list<string>首个唯一字符及目录公共路径最优解法

解法思路 #

要找到整个list<string>里第一个只出现一次的字符，分两步走：

1. 遍历整个列表，统计每个字符的出现次数
2. 再次遍历列表的每个字符，找到第一个计数为1的字符

代码实现 #

#include <list>
#include <unordered_map>
#include <string>

char findFirstUniqueChar(const std::list<std::string>& strList) {
    // 统计所有字符的出现次数
    std::unordered_map<char, int> charCount;
    for (const auto& str : strList) {
        for (char c : str) {
            charCount[c]++;
        }
    }

    // 再次遍历，寻找首个唯一字符
    for (const auto& str : strList) {
        for (char c : str) {
            if (charCount[c] == 1) {
                return c;
            }
        }
    }

    // 无唯一字符时返回特殊值，可根据需求调整
    return '\0';
}

补充说明 #

• 用unordered_map统计的平均时间复杂度为O(1)，整体时间复杂度是O(N)（N为所有字符串的总字符数）
• 如果需要忽略大小写，统计时统一将字符转成小写或大写即可

最优解法思路 #

核心是拆分路径为目录段 + 寻找最长公共前缀，具体步骤：

1. 将每个路径按/分割为目录段数组（比如/a/ab/bc/de会拆成["a", "ab", "bc", "de"]，跳过开头的空段）
2. 以第一个路径的目录段为基准，逐个位置检查所有其他路径的对应段是否相同，直到出现差异或某个路径遍历结束，得到公共目录段
3. 将公共目录段拼接成完整的公共路径
4. 每个原路径去掉公共路径部分，得到相对路径

代码实现 #

#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <sstream>

// 辅助函数：拆分路径为目录段
std::vector<std::string> splitPath(const std::string& path) {
    std::vector<std::string> segments;
    std::stringstream ss(path);
    std::string segment;
    while (std::getline(ss, segment, '/')) {
        if (!segment.empty()) { // 跳过路径开头的空段
            segments.push_back(segment);
        }
    }
    return segments;
}

// 获取所有目录的公共路径
std::string getCommonPath(const std::vector<std::string>& dirs) {
    if (dirs.empty()) return "";

    auto firstSegments = splitPath(dirs[0]);
    size_t commonLen = firstSegments.size();

    for (const auto& dir : dirs) {
        auto segments = splitPath(dir);
        size_t minLen = std::min(commonLen, segments.size());
        size_t i = 0;
        while (i < minLen && firstSegments[i] == segments[i]) {
            i++;
        }
        commonLen = i;
        if (commonLen == 0) break; // 无公共前缀，直接终止
    }

    // 拼接公共路径
    std::string commonPath;
    for (size_t i = 0; i < commonLen; i++) {
        commonPath += "/" + firstSegments[i];
    }
    return commonPath.empty() ? "/" : commonPath; // 处理根目录场景
}

// 提取所有目录的相对路径
std::vector<std::string> getRelativePaths(const std::vector<std::string>& dirs, const std::string& commonPath) {
    std::vector<std::string> relativePaths;
    size_t commonLen = commonPath.size();

    for (const auto& dir : dirs) {
        if (dir == commonPath) {
            relativePaths.push_back(""); // 原路径等于公共路径时，相对路径为空
        } else {
            // 跳过公共路径后的第一个/，直接截取剩余部分
            relativePaths.push_back(dir.substr(commonLen + 1));
        }
    }
    return relativePaths;
}

示例验证 #

• 示例1输入目录列表，getCommonPath返回/a/ab，getRelativePaths返回["bc/de", "cc/fw", "dd", "ee/fg"]
• 示例2输入目录列表，getCommonPath返回/a，getRelativePaths返回["ab/bc/de", "b/cc/fw", "ab/dd", "ab/ee/fg"]

补充说明 #

• 时间复杂度：假设共有M个目录，每个目录平均拆分为K段，整体时间复杂度为O(M*K)，属于线性最优复杂度
• 兼容性：处理了空目录列表、根目录、单个目录等边界场景
• 灵活性：如果输入是list<string>，只需将函数参数改为const std::list<std::string>& dirs即可，逻辑无需调整

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