如何使用Java从两个字符串中打印唯一的字母?

Recently, I attended an interview. They asked me to write a program to print unique alphabets and common characters from two strings. I wrote the code below to print the common characters:

最近，我参加了一次面试。他们让我编写一个程序，从两个字符串中打印唯一的字母和常见字符。我写了下面的代码来打印常见的字符:

String s1 = "I am living in india";
String s2 = "india is a beautiful country";

char[] s1Array = s1.toCharArray();
char[] s2Array = s2.toCharArray();

LinkedHashSet<Character> s1CharSet = new LinkedHashSet<Character>();
LinkedHashSet<Character> s2CharSet = new LinkedHashSet<Character>();

for(char kc : s1Array){
    s1CharSet.add(kc);
}

for(char c: s2Array){
    s2CharSet.add(c);
}

s1CharSet.retainAll(s2CharSet);

if(s1CharSet.size()==0){
    System.out.println("There are no common characters between the two strings");
}
else{
    System.out.println(s1CharSet);
}
}

but they said like they are not satisfied with my answer. I guess it's because they are not expecting retainAll. So, please tell me the right way of programming to satisfy them in the future.

但他们说他们对我的回答不满意。我想那是因为他们不希望得到全部遗产。所以，请告诉我怎样才能在未来让他们满意。

I even Googled but I didn't find any good, understandable links.

我甚至在谷歌上搜索过，但是我没有找到任何好的，可以理解的链接。

So, how to print unique and common characters from two strings without using retainAll?

那么，如何在不使用retainAll的情况下从两个字符串中打印唯一和公共字符呢?

Any code would be appreciated.

任何代码都可以。

8 个解决方案

#1

It is possible the interviewer wanted to check your understanding of the internals of how to solve this problem efficiently, and usage of retainAll() kinda misses the purpose of this task.

很可能面试官想要检查你对如何有效地解决这个问题的内部理解，而retainAll()的使用有点偏离了这个任务的目的。

To implement it "from scratch" one can use several approaches:

要“从头开始”实现它，可以使用以下几种方法:

Similar to your solution - populate two Set objects - one for each string, and then check the difference/common element between them by:

与您的解决方案类似，填充两个Set对象——每个字符串一个，然后通过以下方式检查它们之间的差异/公共元素:
```
for (Character c : set1) {
    if (set2.contains(c)) {
        System.out.println(c);
    }
}
```
You can even use a bitset if the alphabet is known to be constant (and small enough), otherwise a HashSet is fine and will achieve O(n) average case performance.

如果字母表是常量(并且足够小)，甚至可以使用位集，否则HashSet就可以实现O(n)的平均大小写性能。
sort and iterate: sort the two char arrays and iterate together to find common (and unique) characters. While in java there is no real benefit for it (since String is immutable, so you need to create a new char[] anyway) - in other languages, it saves up space and can be done inplace with really little additional space.

排序和迭代:对两个字符数组进行排序，并一起迭代以查找公共(和惟一)字符。虽然在java中，它并没有真正的好处(因为String是不可变的，所以无论如何您都需要创建一个新的char[])——在其他语言中，它节省了空间，并且可以在不需要额外空间的情况下就地完成。

#2

Print unique and common characters from two string without using retainAll.

不使用retainAll从两个字符串中打印唯一和通用字符。

        String firstString = "I am living in india";
        String secondString = "india is a beautiful country";

        HashSet<Character> h1 = new HashSet<Character>(), h2 = new HashSet<Character>();
        for(int i = 0; i < firstString.length(); i++) {
            h1.add(firstString.charAt(i));
        }
        for(int i = 0; i < secondString.length(); i++){
            h2.add(secondString.charAt(i));
        }

        StringBuffer commonSB = new StringBuffer();
        StringBuffer uniqueSB = new StringBuffer();

        for(Character i : h1){
            if(!h2.contains(i)){
               uniqueSB.append(i);
            }else{
               commonSB.append(i);
            };
         }

         for(Character i : h2){
            if(!h1.contains(i)){
               uniqueSB.append(i);
            };
         }

         System.out.println("Common:"+commonSB.toString().replace(" ", ""); 
         System.out.println("Unique:"+uniqueSB.toString().replace(" ", "");

Results:

结果:

Common:danli
Unique:gvmIfebcoutsry

#3

when you are going for an interview and if they ask for silly question like the one you said, then they are not looking for complex Collection framework. They are looking if you can do the same at grass root level with your coding abilities keeping in mind how you write a code that will be able to handle cases even if the data provided goes into millions.

当你去面试的时候，如果他们问一些像你说的那样愚蠢的问题，他们就不会去找复杂的收集框架。他们正在寻找你是否可以在草根层次上用你的编码能力做同样的事情，记住你如何编写一个即使提供的数据达到数百万的代码也能处理各种情况的代码。

This problem can be easily solved by taking an byte[]. We know that char is represented by numeric internally.

这个问题可以通过一个字节[]来轻松地解决。我们知道char在内部由数字表示。

so in the first iteration, just iterate over the chars of the first string(str1) and set the byte location to some constant, say 1.

因此，在第一次迭代中，只需遍历第一个字符串(str1)的字符，并将字节位置设置为某个常数，比如1。

for (int i=0; i<str1.length; i++) {
     byteArr[(int)str.charAt(i)] = 1; // O(1)
}

so in the second iteration, just iterate over the chars of the second string and set the byte location to some constant say 2 only if it is set to 1, and 3 to represent that it is unique to str2.

因此，在第二个迭代中，只需遍历第二个字符串的字符，并将字节位置设置为某个常数，比如只有当它被设置为1时，才将其设置为2，并将其设置为3，以表示它对str2是唯一的。

In the third iteration, just iterate over the byte arr and print the chars(convert the index to char) where ever it is 2 for common and 1/3 for unique.

在第三次迭代中，只需遍历字节arr，并打印字符(将索引转换为char)，其中，公共的为2，唯一的为1/3。

final solution O(n) and scalable.

最终解决方案O(n)和可伸缩。

#4

s1CharSet.retainAll(s2CharSet);

s1CharSet.retainAll(s2CharSet);

Seems like the above line just gave the intersection (A intersection B).

看起来上面这条线给出了交点(一个交点B)

To get all the Unique characcrters you need to get the UNION. A-B + A Intersection B + B-A.

要得到所有你需要的独特的角色，你需要得到工会。A-B + A交点B + B-A。

UPDATE: Reference :Intersect and Union

更新:参考:交联

public class Test {

public static void main(String... args) throws Exception {

    List<String> list1 = new ArrayList<String>(Arrays.asList("A", "B", "C"));
    List<String> list2 = new ArrayList<String>(Arrays.asList("B", "C", "D", "E", "F"));

    System.out.println(new Test().intersection(list1, list2));
    System.out.println(new Test().union(list1, list2));
}

public <T> List<T> union(List<T> list1, List<T> list2) {
    Set<T> set = new HashSet<T>();

    set.addAll(list1);
    set.addAll(list2);

    return new ArrayList<T>(set);
}

public <T> List<T> intersection(List<T> list1, List<T> list2) {
    List<T> list = new ArrayList<T>();

    for (T t : list1) {
        if(list2.contains(t)) {
            list.add(t);
        }
    }

    return list;
}
   }

#5

I would have done something like:

我可能会这样做:

//assume questions treats I and i as the same.
    String s1 = "I am living in india".toLowerCase();
    String s2 = "india is a beautiful country".toLowerCase();

    //Since character is comparable this will maintain the set in alphabetical order when we print it. - well based on the numerical chacacter anyway.
    Set<Character> unique = new TreeSet<Character>(); 
    Set<Character> common = new TreeSet<Character>();

    unique.addAll(Arrays.<Character>asList(ArrayUtils.toObject(s1.toCharArray()))); //Oh java !?!?!
    for(Character c : s2.toCharArray()){
        if(!unique.add(c)){
            common.add(c);
        }
    }

    //Assume question didnt mean to include whitespace
    unique.remove(' ');
    common.remove(' ');

    System.out.println("Unique: " + unique.toString());
    System.out.println("Common: " + common.toString());

This basically just exploits the behaviour of the set add function, that it returns true if the element was not in the set, and false if it was. The set avoids duplication.

这基本上利用了set add函数的行为，如果元素不在集合中，它返回true，如果是false。避免重复。

Gives the output:

给出了输出:

Unique: [a, b, c, d, e, f, g, i, l, m, n, o, r, s, t, u, v, y]
Common: [a, d, i, l, n, t, u]

There are a couple of small points that an interviewer might pick up on:

面试官可能会注意到以下几点:

1) You used the class and not the interface in your LinkedHashSet definitions. This is widely regarded as bad practice and might be taken as showing that you have limited familiarity with Java - ofc, whether that is an issue depends on what level of experience they are interested in..

1)您使用的是类，而不是LinkedHashSet定义中的接口。这被广泛认为是不好的做法，并可能被认为表明你对Java - ofc的熟悉程度有限，这是否是一个问题取决于他们感兴趣的经验水平。

2) Your variable naming. You are never happy as an interviewer if your candidate keeps naming objects "thingy" or functions "someFunction", a natural programmer produces helpful names for objects and functions on the fly. Again, depending on the level of experience they wanted this might or might not be an issue.

2)你的变量命名。作为面试官，如果你的面试官不断地给对象命名“东西”或函数命名“某某函数”，自然程序员就会为动态的对象和函数生成有用的名称。同样，根据他们想要的经验水平，这可能是个问题，也可能不是。

3) They might have been looking for some imagination in interpreting the question, e.g. to ask if whitespace was a "character" in the question, or to sort the output to make it more readable. Or to ask whether to treat I and i as the same or different characters.

3)他们可能一直在寻找解释问题的想象力，例如，询问空格是否是问题中的“字符”，或者对输出进行排序，使其更具可读性。或者问是否要把我和我看成相同或不同的角色。

4) They might have been expecting some knowledge of the timeline of Java development, e.g. to say "Here I used Autoboxing, so it requires a 1.7 or later compiler."

4)他们可能期望了解Java开发的时间轴，例如说“我在这里使用了Autoboxing，所以它需要1.7个或更晚的编译器。”

5) You might just have taken too long, or needed too many syntax hints/corrections.

你可能花了太长时间，或者需要太多的语法提示/更正。

#6

class uniqueCharInTwoString{
    public static void unique(String a, String b){
        HashSet<Character> unique = new HashSet<Character>();
        HashSet<Character> common = new HashSet<Character>();
        for(Character c : a.toCharArray()){
            unique.add(c);
        }
        for(Character c : b.toCharArray()){
            if(!unique.add(c)){
                common.add(c);
            }
        }
        unique.removeAll(common);
        unique.remove(' ');
        common.remove(' ');
        System.out.println(unique);
        System.out.println(common);
    }
    public static void main(String args[]){
        String a = "abdedf";
        String b = "cdfang";
        unique(a,b);
    }
}

#7

This is my solution implementing LinkedHashSet to maintain character order in the strings.

这是我实现LinkedHashSet以维护字符串中的字符顺序的解决方案。

import java.util.LinkedHashSet;
import java.util.Set;

public class CommonCharacters {
 public static void main(String[] args) {
    Pair<String, String> p = getDuplicates("abdxzewxk", "axzmnx");
    System.out.println("Unique:" + p.value1 + "  Common:" + p.value2);
}

public static Pair<String, String> getDuplicates(String s1, String s2) 
{
    Set<Character> xters1 = new LinkedHashSet<Character>();
    Set<Character> xters2 = new LinkedHashSet<Character>();

    for (char c : s1.toCharArray()) {
        xters1.add(c);
    }

    for (char c : s2.toCharArray()) {
        xters2.add(c);
    }

    Set<Character> unique = new LinkedHashSet<>();
    Set<Character> common = new LinkedHashSet<>();

    for (char c : xters1) {
        if (xters2.contains(c))
            common.add(c);
        else
            unique.add(c);
    }

    for (char c : xters2) {
        if (xters1.contains(c))
            common.add(c);
        else
            unique.add(c);
    }

    return new Pair(stringfry(common), stringfry(unique));
}

public static String stringfry(Set<Character> chrs) {
    StringBuilder sb = new StringBuilder();
    chrs.forEach(s -> {
        sb.append(s);
    });
    return sb.toString();
}


static class Pair<E, U> {
    private E value1;
    private U value2;

    public Pair(E value1, U value2) {
        this.value1 = value1;
        this.value2 = value2;
    }
}

#8

Let say for simplicity our strings only consists of lower case characters. Now we can construct two array of length 26 , and count the occurrence of characters . Now compare both arrays , if both have count >0 ,then its common to both string . If count is zero in one and non zero in other , the its unique to that particular string. If both zero the character is not present in either string.

为了简单起见，我们的字符串只包含小写字符。现在我们可以构造两个长度为26的数组，并计算字符的出现次数。现在比较两个数组，如果两个数组都有count >，那么它对两个字符串都是通用的。如果count在1中为0，在另一个中为非0，那么它对于那个特定的字符串是唯一的。如果两个字符都为0，那么两个字符串中的字符都不存在。

The above approach could be used for many similar problems.

上述方法可用于许多类似的问题。

#1