Общие символы в n строках - PullRequest
Новая
       18

Общие символы в n строках

0 голосов
/ 10 февраля 2019

Я пытаюсь создать функцию, которая печатает количество символов, общее для заданных 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 
abcaa
bcbd
bgc
3

есть вероятность того, что один и тот же символ может присутствовать несколько раз в строке, и вы не должны удалять эти символы, вместо этого отметьте no.раз они повторяются в других строках.например, 

 3
 abacd
 aaxyz
 aatre

вывод должен быть 2

будет лучше, если я получу решение в Java

Ответы [ 5 ]

0 голосов
/ 10 февраля 2019

Вы должны преобразовать все String с Set из Character с и сохранить все из первого.В приведенном ниже решении есть много мест, которые можно оптимизировать, но вы должны понимать общую идею. 

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]
0 голосов
/ 10 февраля 2019 
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
0 голосов
/ 10 февраля 2019

Получить список символов для каждой строки: 

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()

0 голосов
/ 10 февраля 2019

Хорошо, если кто-то идет на хэширование: 

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;
}

Это использует сортировку по сегментам, которая дает сложность n + m, но требует 26 сегментов (массив "hash").Мне кажется, что нельзя добиться большего успеха в отношении сложности, так как вам нужно хотя бы раз взглянуть на каждую букву, которая суммирует до n + m.

Insitu лучшее, что вы можете получить, это imho где-то в диапазоне O(n log (n)).

Ваш подход находится где-то в лиге O (n²)

Аддон: если вам нужны символы в виде строки (по сути то же самое, что и выше сcount - длина возвращаемой строки): 

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();
}
0 голосов
/ 10 февраля 2019

Лучшей стратегией для вашей проблемы является использование этого метода: 

public int[] countChars(String s){
    int[] count = new int[26];
    for(char c: s.toCharArray()){
        count[c-'a']++;
    }
    return count;
}

Теперь, если у вас n строк (String [] строк), просто найдите минимум общих символов для каждой буквы: 

int[][] result = new int[n][26]
for(int i = 0; i<strings.length;i++){
    result[i] = countChars(s);
}
// now if you sum the min common chars for each counter you are ready
int commonChars = 0; 
for(int i = 0; i< 26;i++){
    int min = result[0][i];
    for(int i = 1; i< n;i++){
        if(min>result[j][i]){
            min = result[j][i];
        }
    }
    commonChars+=min;
}
...