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

举报
共饮一杯无 发表于 2023/02/21 09:39:37 2023/02/21
【摘要】 单词拆分(字典树、记忆化搜索)给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明:拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1:输入: s = “leetcode”, wordDict = [“leet”, “code”]输出: true 解释: 返回 true因为 “leetco...

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

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

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。