当前位置:网站首页>LeetCode 648(C#)
LeetCode 648(C#)
2022-07-07 15:38:00 【有趣就行】
题目
在英语中,我们有一个叫做 词根(root) 的概念,可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 other(其他),可以形成新的单词 another(另一个)。
现在,给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。
你需要输出替换之后的句子。
示例 1:
输入:dictionary = [“cat”,“bat”,“rat”], sentence = “the cattle was rattled by the battery”
输出:“the cat was rat by the bat”
示例 2:
输入:dictionary = [“a”,“b”,“c”], sentence = “aadsfasf absbs bbab cadsfafs”
输出:“a a b c”
代码
- 正则表达式
using System.Text.RegularExpressions;
public class Solution
{
public string ReplaceWords(IList<string> dictionary, string sentence)
{
foreach (var dic in dictionary)
{
string regex = @$"((?<= )({
dic})\w+|^({
dic})\w+)";
sentence = Regex.Replace(sentence, regex, dic);
}
return sentence;
}
}
- 哈希枚举
public class Solution
{
public string ReplaceWords(IList<string> dictionary, string sentence)
{
ISet<string> set = new HashSet<string>();
foreach (var dic in dictionary)
set.Add(dic);
string[] words = sentence.Split(" ");
for (int i = 0; i < words.Length; i++)
{
string word = words[i];
for (int j = 0; j < word.Length - 1; j++)
{
if (set.Contains(word[0..(j + 1)]))
{
words[i] = word[0..(j + 1)];
break;
}
}
}
return string.Join(" ", words);
}
}
- 前缀树
public class Solution
{
private Trie _root = new Trie();
public string ReplaceWords(IList<string> dictionary, string sentence)
{
foreach (var s in dictionary) Add(s);
StringBuilder sb = new StringBuilder();
foreach (var s in sentence.Split(" "))
sb.Append(Query(s)).Append(" ");
sb.Length = sb.Length - 1;
return sb.ToString();
}
private void Add(string s)
{
Trie p = _root;
for (int i = 0; i < s.Length; i++)
{
int u = s[i] - 'a';
if (p.childer[u] == null)
p.childer[u] = new Trie();
p = p.childer[u];
}
p.isEnd = true;
}
private string Query(string s)
{
Trie p = _root;
for (int i = 0; i < s.Length; i++)
{
int u = s[i] - 'a';
if (p.childer[u] == null) break;
if (p.childer[u].isEnd) return s[0..(i + 1)];
p = p.childer[u];
}
return s;
}
private class Trie
{
public bool isEnd;
public Trie[] childer = new Trie[26];
}
}
边栏推荐
- Jenkins发布uniapp开发的H5遇到的问题
- LeetCode 1774. The dessert cost closest to the target price is one question per day
- 麒麟信安中标国网新一代调度项目!
- 【Seaborn】组合图表:FacetGrid、JointGrid、PairGrid
- LeetCode 1186. 删除一次得到子数组最大和 每日一题
- Skimage learning (2) -- RGB to grayscale, RGB to HSV, histogram matching
- MySQL implements the query of merging two fields into one field
- LeetCode 152. 乘积最大子数组 每日一题
- SlashData开发者工具榜首等你而定!!!
- Seaborn数据可视化
猜你喜欢
随机推荐
LeetCode 1654. The minimum number of jumps to get home one question per day
The top of slashdata developer tool is up to you!!!
LeetCode 1774. The dessert cost closest to the target price is one question per day
[source code interpretation] | source code interpretation of livelistenerbus
【Seaborn】组合图表、多子图的实现
LeetCode 312. 戳气球 每日一题
LeetCode 1696. 跳跃游戏 VI 每日一题
第二十四届中国科协湖南组委会调研课题组一行莅临麒麟信安调研考察
Sator launched Web3 game "satorspace" and launched hoobi
MySQL usage notes 1
MySQL implements the query of merging two fields into one field
AI来搞财富分配比人更公平?来自DeepMind的多人博弈游戏研究
rpcms获取指定分类下的文章的方法
LeetCode 1049. 最后一块石头的重量 II 每日一题
Flask搭建api服务-SQL配置文件
QT picture background color pixel processing method
鲲鹏开发者峰会2022 | 麒麟信安携手鲲鹏共筑计算产业新生态
Flask build API service SQL configuration file
第九届 蓝桥杯 决赛 交换次数
【饭谈】那些看似为公司着想,实际却很自私的故事 (一:造轮子)