时间戳

首页 > 解决方案 > 根据与输入字符串匹配的单词对字符串数组进行排序

algorithm - 根据与输入字符串匹配的单词对字符串数组进行排序

问题描述

我无法在编码竞赛中找到以下问题的任何解决方案。

问题：我们输入了由下划线分隔的“好词”字符串和用户评论列表（基本上是字符串数组，其中每个数组元素都有一些由下划线分隔的单词）。我们必须对用户评论列表进行排序，以便具有更多好词的元素排在第一位。

Example:

input:

good words: "pool_clean_food".

user review array:["food_bedroom_environment","view_sea_desert","clean_pool_table"].

output: [2,0,1]

Explanation:

Array[2]="clean_pool_table" having 2 good words i.e. pool and clean
Array[0]="food_bedroom_environment" having 1 good word i.e. food
Array[1]="view_sea_desert" having 0 good word i.e. nil

How can I approach the problem, which data structure shall I use so that my code can handle large inputs?

标签： algorithmdata-structures

解决方案

  • 用下划线分割输入的好词，并存储在一个哈希集中。

  • 现在对于每个评论，最初分配分数 0。也用下划线分割单词，并一一检查这些单词是否存在于哈希集中。如果该单词存在，则将该单词的得分加 1。

  • 现在将每条评论视为<review, score>一对，并根据它们的得分值按升序对这些评论进行排序。您可以为此使用任何标准排序O(nlogn)算法。

代替 hashset，你可以使用 Trie 来加速算法，以防单词太大。

推荐阅读