当前位置:网站首页>LeetCode 648. Word replacement
LeetCode 648. Word replacement
2022-07-07 14:19:00 【Sasakihaise_】
【 Hash + string manipulation 】 take dictionary Put the words in HashSet in , Record the length of words during the addition process , Convenience is right sentence Prefix the words in .
class Solution {
// Hash + String interception 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 tree 】 Yes dictionary Word construction in , Traverse sentence The words in , The prefix that matches first can be returned .
class Solution {
// Dictionary tree 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();
}
}
【 Dictionary tree + Hash table writing 】
class Solution {
// Dictionary tree 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);
}
}
边栏推荐
- 用例图
- 参数关键字Final,Flags,Internal,映射关键字Internal
- Seven propagation behaviors of transactions
- The meaning of variables starting with underscores in PHP
- Wired network IP address of VMware shared host
- Bashrc and profile
- Leetcode——剑指 Offer 05. 替换空格
- Details of redis core data structure & new features of redis 6
- NDK beginner's study (1)
- CSMA/CD 载波监听多点接入/碰撞检测协议
猜你喜欢
最长上升子序列模型 AcWing 1012. 友好城市
UML state diagram
UML 顺序图(时序图)
设备故障预测机床故障提前预警机械设备振动监测机床故障预警CNC震动无线监控设备异常提前预警
Wired network IP address of VMware shared host
Codes de non - retour à zéro inversés, codes Manchester et codes Manchester différentiels couramment utilisés pour le codage des signaux numériques
LeetCode每日一题(636. Exclusive Time of Functions)
OAuth 2.0 + JWT protect API security
Dry goods | summarize the linkage use of those vulnerability tools
Details of redis core data structure & new features of redis 6
随机推荐
Cargo placement problem
交换机和路由器的异同
Leetcode——236. The nearest common ancestor of binary tree
Oracle non automatic submission solution
Mysql怎样控制replace替换的次数?
LeetCode每日一题(636. Exclusive Time of Functions)
Excusez - moi, l'exécution a été réussie lors de l'utilisation des données de puits SQL Flink à Kafka, mais il n'y a pas de nombre dans Kafka
UML state diagram
Realization of search box effect [daily question]
3D detection: fast visualization of 3D box and point cloud
Use day JS let time (displayed as minutes, hours, days, months, and so on)
Vmware 与主机之间传输文件
Cascading update with Oracle trigger
请问指南针股票软件可靠吗?交易股票安全吗?
Interface automation test - solution of data dependency between interfaces
IP address home location query
Common response status codes
GAN发明者Ian Goodfellow正式加入DeepMind,任Research Scientist
PC端页面如何调用QQ进行在线聊天?
Cesium 已知一点经纬度和距离求另一个点的经纬度