华为机试：快速人名查找

最新推荐文章于 2024-06-01 20:57:12 发布

OceanStar的学习笔记

最新推荐文章于 2024-06-01 20:57:12 发布

阅读量1.7k

点赞数

分类专栏：算法与数据结构文章标签：华为

原文链接： https://www.online1987.com/%e5%bf%ab%e9%80%9f%e4%ba%ba%e5%90%8d%e6%9f%a5%e6%89%be/

版权

算法与数据结构专栏收录该内容

1121 篇文章 78 订阅

订阅专栏

题目描述

华为机试：快速人名查找

题目来源

题目解析

思路：

先将输入按照,风格得到一个字符串数组
然后遍历这个数组，针对每一个人的名字：
- 按照,切割，然后从左到右模型尝试匹配
- 什么时候停止呢？
  - 当names匹配完成 || exp匹配完成了
    - 只有names和exp都全部匹配完成了，才满足要求
- 对于names中的每一个name：
  - 第一个字母必须能用到
  - 然后每一个name可能会消耗多个exp的字符

#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;



// 1. 先对字符串进行切割
std::vector<std::string> strSplit(std::string str, char ch){
    std::vector<std::string> ans;
    int pos = 0;
    while ((pos = str.find(ch, 0)) != -1){
        ans.push_back(str.substr(0, pos));
        str = str.substr(pos + 1);
    }
    if(!str.empty()){
        ans.push_back(str);
    }
    return ans;
}

// 一定要用到每个单词
// 前i个字符去匹配exp的前j个字符
bool dfs(std::vector<std::string> &person, int pi, std::string exp, int ej){
    // 有任意一方已经使用完了
   if(pi == person.size() || ej == exp.size()){
       return (pi == person.size() && ej == exp.size()); // 只有两方同时使用完了，才是ok的
   }

    // 不需要完全匹配掉

   // 开始匹配，对于当前person[pi]
    // 其首字母一定要匹配，否则这个字符就不能用
    // 对于当前person[i]，它可以取用person[0...]去匹配exp[ej]
    // zhang seng
    // zhas
    std::string name = person[pi];

    // 首字母不匹配
    if(name[0] != exp[ej]){
        return false;
    }

    // name和exp开始匹配
    // name消耗多个exp
    int cnt = 1;
    while (cnt < name.size() && ej + cnt < exp.size() && name[cnt] == exp[ej + cnt]){
        if(dfs(person, pi + 1, exp, ej + cnt + 1)){
            return true;
        }
        cnt++;
    }

    // 首字母匹配，那么直接进行下一个匹配
    return dfs(person, pi + 1, exp, ej  + 1 );
}



int main(){
    std::string input, exp, ans;
    getline(std::cin, input);
    std::cin >> exp;
    auto names = strSplit(input, ',');
    for (const auto & name : names) {
        auto person = strSplit(name, ' ');
        if(dfs(person, 0, exp, 0)){
            ans = ans.empty() ? name : ans + "," + name;
        }
    }

    std::cout << ans << "\n";
}