当前位置:网站首页>LeetCode 648(C#)
LeetCode 648(C#)
2022-07-07 19:20:00 【Just be interesting】
subject
In English , We have one called Root (root) The concept of , You can add other words after the root to form another longer word —— We call it Inheritance words (successor). for example , Root an, Follow the word other( other ), Can form new words another( the other one ).
Now? , Given a dictionary consisting of many roots dictionary And a sentence formed by separating words with spaces sentence. You need to replace all the inherited words in the sentence with roots . If an inherited word has many roots that can form it , Replace it with the shortest root .
You need to output the replaced sentences .
Example 1:
Input :dictionary = [“cat”,“bat”,“rat”], sentence = “the cattle was rattled by the battery”
Output :“the cat was rat by the bat”
Example 2:
Input :dictionary = [“a”,“b”,“c”], sentence = “aadsfasf absbs bbab cadsfafs”
Output :“a a b c”
Code
- Regular expressions
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;
}
}
- Hash enumeration
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);
}
}
- Prefix tree
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];
}
}
边栏推荐
猜你喜欢
Creative changes brought about by the yuan universe
Scientists have observed for the first time that the "electron vortex" helps to design more efficient electronic products
完整的电商系统
[information security laws and regulations] review
微服务远程Debug,Nocalhost + Rainbond微服务开发第二弹
3. About cookies
多个kubernetes集群如何实现共享同一个存储
99% of people don't know that privatized deployment is also a permanently free instant messaging software!
Tips and tricks of image segmentation summarized from 39 Kabul competitions
Continuous test (CT) practical experience sharing
随机推荐
How many times is PTA 1101 B than a
反爬虫的重点:识别爬虫
First time in China! The language AI strength of this Chinese enterprise is recognized as No.2 in the world! Second only to Google
Solve the error reporting problem of rosdep
Hutool - lightweight DB operation solution
2022-07-04 matlab读取视频帧并保存
AI写首诗
博睿数据入选《2022爱分析 · IT运维厂商全景报告》
How much does it cost to develop a small program mall?
Flipping Game(枚举)
L1-019 who falls first (Lua)
鸿蒙智能家居【1.0】
最长公共前缀(leetcode题14)
从39个kaggle竞赛中总结出来的图像分割的Tips和Tricks
Wechat web debugging 8.0.19 replace the X5 kernel with xweb, so the X5 debugging method can no longer be used. Now there is a solution
Thread factory in thread pool
How to estimate the value of "not selling pens" Chenguang?
ES6 note 1
Zhong Xuegao wants to remain innocent in the world
国内首次!这家中国企业的语言AI实力被公认全球No.2!仅次于谷歌