当前位置:网站首页>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];
}
}
边栏推荐
- 如何选择合适的自动化测试工具?
- [source code interpretation] | source code interpretation of livelistenerbus
- A tour of grpc:03 - proto serialization / deserialization
- 如何在博客中添加Aplayer音乐播放器
- User defined view essential knowledge, Android R & D post must ask 30+ advanced interview questions
- LeetCode 213. 打家劫舍 II 每日一题
- 麒麟信安携异构融合云金融信创解决方案亮相第十五届湖南地区金融科技交流会
- skimage学习(2)——RGB转灰度、RGB 转 HSV、直方图匹配
- LeetCode 1043. Separate the array to get the maximum and daily questions
- 第二十四届中国科协湖南组委会调研课题组一行莅临麒麟信安调研考察
猜你喜欢
SlashData开发者工具榜首等你而定!!!
skimage学习(3)——使灰度滤镜适应 RGB 图像、免疫组化染色分离颜色、过滤区域最大值
Siggraph 2022 best technical paper award comes out! Chen Baoquan team of Peking University was nominated for honorary nomination
Sator launched Web3 game "satorspace" and launched hoobi
Sator推出Web3游戏“Satorspace” ,并上线Huobi
skimage学习(3)——Gamma 和 log对比度调整、直方图均衡、为灰度图像着色
PLC: automatically correct the data set noise, wash the data set | ICLR 2021 spotlight
Reflections on "product managers must read: five classic innovative thinking models"
QML初学
Lowcode: four ways to help transportation companies enhance supply chain management
随机推荐
How to choose the appropriate automated testing tools?
邮件服务器被列入黑名单,如何快速解封?
LeetCode 403. Frog crossing the river daily
Flask build API service SQL configuration file
[video / audio data processing] Shanghai daoning brings you elecard download, trial and tutorial
LeetCode 213. 打家劫舍 II 每日一题
LeetCode 312. 戳气球 每日一题
Blue Bridge Cup final XOR conversion 100 points
管理VDI的几个最佳实践
Nerf: the ultimate replacement for deepfake?
How to mount the original data disk without damage after the reinstallation of proxmox ve?
[Seaborn] implementation of combined charts and multi subgraphs
Flask搭建api服务-SQL配置文件
Skimage learning (2) -- RGB to grayscale, RGB to HSV, histogram matching
科普达人丨一文弄懂什么是云计算?
[Seaborn] combination chart: pairplot and jointplot
Pycharm IDE下载
A tour of grpc:03 - proto serialization / deserialization
麒麟信安携异构融合云金融信创解决方案亮相第十五届湖南地区金融科技交流会
《产品经理必读:五种经典的创新思维模型》的读后感