n 个字符串中的常用字符

Question

我正在尝试制作一个函数来打印给定 n 个字符串中常见的字符数。（注意字符可以多次使用）我正在努力对 n 个字符串执行此操作但是我为 2 个字符串执行了此操作，而没有任何字符重复多次。我已经发布了我的代码。public class CommonChars {    public static void main(String[] args) {        String str1 = "abcd";        String str2 = "bcde";        StringBuffer sb = new StringBuffer();        // get unique chars from both the strings        str1 = uniqueChar(str1);        str2 = uniqueChar(str2);        int count = 0;        int str1Len = str1.length();        int str2Len = str2.length();        for (int i = 0; i < str1Len; i++) {            for (int j = 0; j < str2Len; j++) {                // found match stop the loop                if (str1.charAt(i) == str2.charAt(j)) {                    count++;                    sb.append(str1.charAt(i));                    break;                }            }        }           System.out.println("Common Chars Count : " + count + "\nCommon Chars :" +         sb.toString());    }    public static String uniqueChar(String inputString) {        String outputstr="",temp="";        for(int i=0;i<inputstr.length();i++) {            if(temp.indexOf(inputstr.charAt(i))<0) {                temp+=inputstr.charAt(i);            }        }        System.out.println("completed");        return temp;    }}3 abcaabcbdbgc3他们可能有机会在一个字符串中多次出现相同的字符，并且您不应该消除这些字符而是检查否。他们在其他字符串中重复的次数。例如 3 abacd aaxyz aatre输出应该是 2如果我在java中得到解决方案会更好

Answer 1

您必须将所有Strings 转换为Setof Characters 并保留第一个中的所有内容。下面的解决方案有很多可以优化的地方，但你应该理解一般的想法。

import java.util.Arrays;

import java.util.Collection;

import java.util.Collections;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

public class Main {

    public static void main(String[] args) {

        List<String> input = Arrays.asList("jonas", "ton", "bonny");

        System.out.println(findCommonCharsFor(input));

    }

    public static Collection<Character> findCommonCharsFor(List<String> strings) {

        if (strings == null || strings.isEmpty()) {

            return Collections.emptyList();

        }

        Set<Character> commonChars = convertStringToSetOfChars(strings.get(0));

        strings.stream().skip(1).forEach(s -> commonChars.retainAll(convertStringToSetOfChars(s)));

        return commonChars;

    }

    private static Set<Character> convertStringToSetOfChars(String string) {

        if (string == null || string.isEmpty()) {

            return Collections.emptySet();

        }

        Set<Character> set = new HashSet<>(string.length() + 10);

        for (char c : string.toCharArray()) {

            set.add(c);

        }

        return set;

    }

}

上面的代码打印：

[n, o]

Answer 2

好吧，如果一个人去散列：

public static int uniqueChars(String first, String second) {

    boolean[] hash = new boolean[26]; 

    int count = 0;

    //reduce first string to unique letters

    for (char c : first.toLowerCase().toCharArray()) {

        hash[c - 'a'] = true;

    }

    //reduce to unique letters in both strings

    for(char c : second.toLowerCase().toCharArray()){

        if(hash[c - 'a']){

            count++; 

            hash[c - 'a'] = false;

        }

    }

    return count;

}

这是使用 bucketsort，它给出了 n+m 的复杂度，但需要 26 个桶（“散列”数组）。Imo 在复杂性方面不能做得更好，因为您需要至少查看每个字母一次，总和为 n + m。

Insitu 你能得到的最好的结果是在 O(n log(n) ) 范围内的某个地方。

你的方法是在 O(n²) 的联盟中的某个地方

插件：如果您需要将字符作为字符串（本质上与上面相同，计数是返回的字符串的长度）：

public static String uniqueChars(String first, String second) {

    boolean[] hash = new boolean[26]; 

    StringBuilder sb = new StringBuilder();

    for (char c : first.toLowerCase().toCharArray()) {

        hash[c - 'a'] = true;

    }

    for(char c : second.toLowerCase().toCharArray()){

        if(hash[c - 'a']){

            sb.append(c);

            hash[c - 'a'] = false;

        }

    }

    return sb.toString();

}

Answer 3

获取每个字符串的字符列表：

List<Character> chars1 = s1.chars()    // list of chars for first string

            .mapToObj(c -> (char) c)

            .collect(Collectors.toList());

List<Character> chars2 = s2.chars()    // list of chars for second string

            .mapToObj(c -> (char) c)

            .collect(Collectors.toList());

然后使用retainAll方法：

chars1.retainAll(chars2);  // retain in chars1 only the chars that are contained in the chars2 also

System.out.println(chars1.size());

如果您想获得唯一字符的数量，只需使用Collectors.toSet()而不是toList()

Answer 4

public static String getCommonCharacters(String... words) {

    if (words == null || words.length == 0)

        return "";

    Set<Character> unique = words[0].chars().mapToObj(ch -> (char)ch).collect(Collectors.toCollection(TreeSet::new));

    for (String word : words)

        unique.retainAll(word.chars().mapToObj(ch -> (char)ch).collect(Collectors.toSet()));

    return unique.stream().map(String::valueOf).collect(Collectors.joining());

}

另一个不创建临时变量Set并使用Character.

public static String getCommonCharacters(String... words) {

    if (words == null || words.length == 0)

        return "";

    int[] arr = new int[26];

    boolean[] tmp = new boolean[26];

    for (String word : words) {

        Arrays.fill(tmp, false);

        for (int i = 0; i < word.length(); i++) {

            int pos = Character.toLowerCase(word.charAt(i)) - 'a';

            if (tmp[pos])

                continue;

            tmp[pos] = true;

            arr[pos]++;

        }

    }

    StringBuilder buf = new StringBuilder(26);

    for (int i = 0; i < arr.length; i++)

        if (arr[i] == words.length)

            buf.append((char)('a' + i));

    return buf.toString();

}

演示

System.out.println(getCommonCharacters("abcd", "bcde"));  // bcd