Java: 确定一个单词是否包含可以在另一个单词中找到的字母？

Question

例如：如果您有一个字符串 "magikarp"，并且您针对 "karma" 对其进行了测试，这将是正确的，因为构成 "karma" 的所有字母都可以在 "magikarp" 中找到。

"kipp" 会 return 错误，因为 "magikarp."

中只有一个 "p"

这是我现在的尝试，但我认为它不是很有效，而且对于一个字母多次出现的情况，它return不正确。

private boolean containsHelper(String word, String word2){      
    for (int i = 0; i < word2.length(); i ++){
        if (!word.contains(String.valueOf(word2.charAt(i)))){
            return false;
        }
    }
    return true;
}

Answer 1

我这里不写程序，但是让你知道怎么做。考虑到复杂性，有两种方法可以做到这一点：

1) 如果您确定字符串中只有 a-z/A-Z 个字符，则取一个大小为 26 的数组。遍历第一个字符串并将出现的字符数放在各自的指数。比如说你有 String "aabcc"。现在数组看起来像 [2,1,2,0,...0]。现在遍历第二个字符串，在每个字符处，从数组中相应字符位置减去 1 并检查结果值。如果值小于 0，则 return 为假。例如，您有 "aacd"。当你在 d 时，你会做 (0-1)，结果 -1 小于 0，因此 return false.

2) 对每个String中的字符进行排序，然后比较

Answer 2

可能的算法是从第二个单词中删除第一个单词中没有出现的所有字母，对两个单词进行排序，然后比较它们。

这是在 Java 8 中实现该目标的合理方法：

List<Integer> wordChars = word.chars().sorted().collect(Collectors.toList());
List<Integer> searchChars = search.chars()
    .filter(wordChars::contains).sorted().collect(Collectors.toList());
return wordChars.equals(searchChars);

Answer 3

您需要确保对于第二个字符串中出现的任何字符c，c在第二个字符串中出现的次数不大于 c 在第一个字符串中出现的次数。

解决这个问题的一个有效方法是使用 hashmap 来存储第一个字符串的字符数，然后循环遍历第二个字符串中的字符来检查它们的总数是否不大于第一个字符串中的总数。在最坏的情况下，时间和 space 复杂度为 O(n)，其中 n 是输入字符串的长度。

下面是供您参考的示例代码：

import java.util.HashMap;
import java.util.Map;

public class HashExample {

    public static void main(String[] args) {
        System.out.println(containsHelper("magikarp", "karma"));     // true
        System.out.println(containsHelper("magikarp", "kipp"));      // false    
    }

    private static boolean containsHelper(String word, String word2) {

        Map<Character, Integer> hm = new HashMap<>();

        for (int i = 0; i < word.length(); i++) {
            Character key = word.charAt(i);
            int count = 0;

            if (hm.containsKey(key)) {
                count = hm.get(key);
            }    
            hm.put(key, ++count);
        }

        for (int i = 0; i < word2.length(); i++) {
            Character key = word2.charAt(i);

            if (hm.containsKey(key)) {
                int count = hm.get(key);

                if (count > 0) {
                    hm.put(key, --count);
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}

Answer 4

由于您只检查字符，因此使用 indexOf 并检查它是否 return -1 会更有效，因为 contains 本身调用 indexOf但还有一些其他装饰...

但是，我认为将 String 转换为 char 数组并在找到它们时将其删除会更简单，这也可以处理多次出现的情况。

所以你的算法看起来像这样:

private final boolean containsHelper(final String word, final String word2)
{
    char[] secondWordAsCharArray = word2.toCharArray();
    char[] firstWordAsCharArray = word.toCharArray();

    Arrays.sort(firstWordAsCharArray);//Make sure to sort so we can use binary search.

    int index = 0;
    for(int i = 0; i++ < secondWordAsCharArray.length;)
    {
        index = Arrays.binarySearch(firstWordAsCharArray, secondWordAsCharArray[i]);//Binary search is a very performant search algorithm

        if(index == -1)
            return false;
        else
            firstWordAsCharArray[index] = ''; //A SENTINEL value, set the char a value you are sure that will never be in word2.
    }
}

基本上，我做的是：

将两个单词都转换为字符数组以使其更容易。
对我们检查的单词的字符数组进行排序，以便我们可以使用二进制搜索。
遍历第二个单词的所有字符。
使用二进制搜索算法检索索引（据我所知，这是一种非常高效的 char 算法）。
如果索引为 -1，则未找到，因此我们可以 return false。
否则请确保我们取消设置字符。

Java: 确定一个单词是否包含可以在另一个单词中找到的字母？

Java: Determining if a word contains letters that can be found in another word?

java

string

contains