当前位置:网站首页>LeetCode 648. 单词替换
LeetCode 648. 单词替换
2022-07-07 12:15:00 【Sasakihaise_】
【哈希+字符串处理】将dictionary中的单词放到HashSet中,在添加过程中记录单词的长度,方便对sentence中的单词取前缀。
class Solution {
// 哈希+字符串截取 12:41
public String replaceWords(List<String> dictionary, String sentence) {
Set<String> set = new HashSet();
Set<Integer> length = new HashSet();
for (var st: dictionary) {
set.add(st);
length.add(st.length());
}
List<Integer> l = new ArrayList(length);
Collections.sort(l);
String[] strs = sentence.split(" ");
int n = l.size();
StringBuilder sb = new StringBuilder();
for (var str: strs) {
sb.append(" ");
var flag = 0;
for (var i = 0; i < n; i++) {
var m = l.get(i);
if (m >= str.length()) {
break;
} else {
var st = str.substring(0, m);
if (set.contains(st)) {
flag = 1;
sb.append(st);
break;
}
}
}
if (flag == 0) {
sb.append(str);
}
}
return sb.toString().strip();
}
}
【字典树】对dictionary中的单词建树,遍历sentence中的单词,最先匹配到的前缀返回即可。
class Solution {
// 字典树 1:15 33
class Trie {
Trie[] map = new Trie[26];
boolean is_end;
}
Trie root = new Trie();
public void add(String str) {
Trie node = root;
for (var i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (node.map[c - 'a'] != null) {
node = node.map[c - 'a'];
} else {
Trie trie = new Trie();
node.map[c - 'a'] = trie;
node = trie;
}
}
node.is_end = true;
}
public String pre(StringBuilder sb, String str) {
Trie node = root;
for (var i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (node.map[c - 'a'] == null) {
return str;
} else {
sb.append(c);
node = node.map[c - 'a'];
if (node.is_end) {
return sb.toString();
}
}
}
return str;
}
public String replaceWords(List<String> dictionary, String sentence) {
for (var str: dictionary) {
add(str);
}
String[] strs = sentence.split(" ");
StringBuilder sb = new StringBuilder();
for (var str: strs) {
sb.append(pre(new StringBuilder(), str));
sb.append(" ");
}
return sb.toString().strip();
}
}
【字典树+哈希表写法】
class Solution {
// 字典树 10:05 10:16
class Trie {
Map<Character, Trie> map = new HashMap();
boolean endOfWord = false;
}
Trie root = new Trie();
public void add(String str) {
Trie node = root;
for (var i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (node.map.containsKey(c)) {
node = node.map.get(c);
} else {
Trie trie = new Trie();
node.map.put(c, trie);
node = trie;
}
}
node.endOfWord = true;
}
public String prefix(String str) {
Trie node = root;
StringBuilder sb = new StringBuilder();
for (var i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (node.map.containsKey(c)) {
sb.append(c);
node = node.map.get(c);
if (node.endOfWord) {
return sb.toString();
}
} else {
return str;
}
}
return str;
}
public String replaceWords(List<String> dictionary, String sentence) {
for (var str: dictionary) {
add(str);
}
String strs[] = sentence.split(" ");
for (var i = 0; i < strs.length; i++) {
strs[i] = prefix(strs[i]);
}
return String.join(" ", strs);
}
}
边栏推荐
- Excuse me, when using Flink SQL sink data to Kafka, the execution is successful, but there is no number in Kafka
- [network security] SQL injection syntax summary
- Attribute keywords aliases, calculated, cardinality, ClientName
- 请问,redis没有消费消息,都在redis里堆着是怎么回事?用的是cerely 。
- Introduction to sakt method
- Mysql怎样控制replace替换的次数?
- AutoCAD - how to input angle dimensions and CAD diameter symbols greater than 180 degrees?
- "Song of ice and fire" in the eleventh issue of "open source Roundtable" -- how to balance the natural contradiction between open source and security?
- 高等數學---第八章多元函數微分學1
- Selenium Library
猜你喜欢
Hands on Teaching: XML modeling
UML sequence diagram (sequence diagram)
AI talent cultivation new ideas, this live broadcast has what you care about
"New red flag Cup" desktop application creativity competition 2022
. Net core about redis pipeline and transactions
XML文件的解析操作
[Reading stereo matching papers] [III] ints
Leetcode simple question sharing (20)
Battle Atlas: 12 scenarios detailing the requirements for container safety construction
2022-7-6 sigurg is used to receive external data. I don't know why it can't be printed out
随机推荐
3D Detection: 3D Box和点云 快速可视化
请问,PTS对数据库压测有好方案么?
Advanced Mathematics - Chapter 8 differential calculus of multivariate functions 1
Es log error appreciation -limit of total fields
gvim【三】【_vimrc配置】
3D detection: fast visualization of 3D box and point cloud
Selenium Library
Arm cortex-a9, mcimx6u7cvm08ad processor application
IP address home location query full version
請問,在使用flink sql sink數據到kafka的時候出現執行成功,但是kafka裏面沒有數
课设之百万数据文档存取
AI人才培育新思路,这场直播有你关心的
THINKPHP框架的优秀开源系统推荐
最长上升子序列模型 AcWing 1014. 登山
"New red flag Cup" desktop application creativity competition 2022
The longest ascending subsequence model acwing 482 Chorus formation
oracle 非自动提交解决
Hands on Teaching: XML modeling
Is it safe to open an account online now? Which securities company should I choose to open an account online?
libSGM的horizontal_path_aggregation程序解读