单词拆分(字典树、记忆化搜索)、字母异位词分组(哈希表、字符串）、定义一个类Generator(散列表)

单词拆分(字典树、记忆化搜索)

给定一个非空字符串 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>()));
    }
}

本文内容到此结束了，
如有收获欢迎点赞👍收藏💖关注✔️，您的鼓励是我最大的动力。
如有错误❌疑问💬欢迎各位大佬指出。
保持热爱，奔赴下一场山海。🏃🏃🏃