单词拆分(字典树、记忆化搜索)
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true 解释: 返回 true
因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true 解释: 返回 true
因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
解答：
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int length = s.length();
int size = wordDict.size();
if (length == 0) {
return true;
}
if (size == 0) {
return false;
}
boolean[] dp = new boolean[length];
for (int i = 0; i < length; i++) {
for (int j = 0; j < size; j++) {
String now = wordDict.get(j);
if (i < now.length()) {
String test = s.substring(0, i + 1);
if (now.equals(test)) {
dp[i] = true;
break;
}
}
if (i >= now.length()) {
String test = s.substring(i - now.length() + 1, i + 1);
if (dp[i - now.length()] && test.equals(now)) {
dp[i] = true;
break;
}
}
}
}
return dp[length - 1];
}
}
字母异位词分组(哈希表、字符串）
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 示例:
输入:[eat", "tea", "tan", "ate", "nat", "bat"]
输出:[[ate","eat","tea"],["nat","tan"],["bat"]]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
解答：
import java.util.*;
public class GroupAnagrams {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, ArrayList<String>> map = new HashMap<>();
for (String str : strs) {
char[] cs = str.toCharArray();
Arrays.sort(cs);
String key = String.valueOf(cs);
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(str);
}
return new ArrayList(map.values());
}
public List<List<String>> groupAnagrams2(String[] strs) {
if (strs.length <= 0) {
return new ArrayList<>();
}
HashMap<String, ArrayList<String>> map = new HashMap<>();
for (String str : strs) {
char[] cs = str.toCharArray();
int[] count = new int[26];
for (char c : cs) {
++count[c - 'a'];
}
StringBuilder s = new StringBuilder("");
for (int num : count) {
s.append(num);
}
String key = String.valueOf(s);
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(str);
}
return new ArrayList(map.values());
}
}
定义一个类Generator(散列表)
定义一个类 Generator（生成器类），它可以在每次调用其 next()方法时，产生由你 最喜欢的电影（如 Snow White 或 Star Wars）的字符构成的名字（作为 String 对象）。在字 符列表中的电影名用完之后，循环到这个字符列表的开始处。使用这个生成器来填充数组、 ArrayList、LinkedList、HashSet，然后打印每一个容器。
解答：
import java.util.*;
public class MovieGenerator {
private String[] movies = new String[] { "SS", "DD", "HH", "FF", "XX", "ZZ" };
private int i = 0;
public String next() {
return movies[i++ % movies.length];
}
public String[] getMovies() {
return movies;
}
public Collection<String> fill(Collection<String> collection) {
for (int i = 0; i < 8; i++) {
collection.add(next());
}
return collection;
}
public static void main(String[] args) {
MovieGenerator generator = new MovieGenerator();
System.out.println(Arrays.toString(generator.getMovies()));
System.out.println(generator.fill(new ArrayList<String>()));
System.out.println(generator.fill(new LinkedList<String>()));
System.out.println(generator.fill(new HashSet<String>()));
}
}
本文内容到此结束了， 如有收获欢迎点赞????收藏????关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问????欢迎各位大佬指出。 主页：共饮一杯无的博客汇总????????
保持热爱，奔赴下一场山海。????????????