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

Question

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

7

最近，我参加了一次面试。面试官要求我编写一个程序来打印两个字符串中独特字符和相同字符。我编写了以下代码以打印相同字符：

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

但是他们说他们对我的回答不满意。我猜这是因为他们没有想到使用retainAll。所以，请告诉我未来编程的正确方法，以满足他们的要求。

我甚至在谷歌上搜索了，但没有找到任何好的、易懂的链接。

那么，如何打印两个字符串中唯一和共同的字符，而不使用retainAll呢？

任何代码都将不胜感激。

- MMMMS

2

你能具体说明一下比“他们对我的回答不满意”更多吗？你的代码有什么问题？ - Mureinik

3

你编写了一个有效的程序。如果“他们”对你的回答不满意，你需要询问“他们”想要看到什么。正确的编程方式是满足未来需求的关键。 - Sergey Kalinichenko

1

@MuratK。因为这样做效率非常低（平均情况下，与OP的解决方案相比，时间复杂度是四次方级别而不是线性级别）。 - amit

1

@MuratK。在ArrayList中使用contains()是对集合进行线性搜索，因此它是O(n)操作。如果对n个元素执行此操作，则得到O(n^2)。另一方面，retainAll()可以在HashSet上实现（我假设它确实这样做了-没有验证），并且可以在线性时间内简单地完成，因此OP代码的复杂度为O(n)。 - amit

1

不，大多数印度人使用“字母表”来表示字母或字符，这是错误的。字母表是一组字母，如拉丁字母A-Z。A是一个“字母”，而不是字母表。 - phuclv

显示剩余8条评论

10个回答

3

当你参加面试时，如果他们问像你说的那样的愚蠢问题，那么他们不是在寻找一个复杂的集合框架。他们想知道你是否能够以基础编码能力完成同样的工作，考虑到你如何编写代码，使其能够处理即使提供的数据达到数百万的情况。

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

因此，在第一次迭代中，只需迭代第一个字符串（str1）的字符并将字节位置设置为某个常量，比如1。

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

在第二次迭代中，只需遍历第二个字符串的字符，并将字节位置设置为某个常量，例如2，仅当它设置为1时，而3表示它是str2中唯一的。

在第三次迭代中，只需遍历字节数组并打印字符（将索引转换为字符），其中2表示共同的，1/3表示唯一的。

最终解决方案O(n)且可扩展。

- rituparna bhattacharyya

2

不使用 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(" ", "");

结果：

Common:danli
Unique:gvmIfebcoutsry

- Dhaval Patel

为什么没有使用 LinkedHashSet？ - MMMMS

如果您想保持插入顺序，请使用LinkedHashSet，否则请使用HashSet。 HashSet不维护任何顺序，而LinkedHashSet像List接口一样维护元素的排序顺序。 - Dhaval Patel

空格不是字母，所以不应该打印空格，对吧？ - MMMMS

没错，你说得对。我们可以在输出上使用 string.replace(" ", "") 方法。 - Dhaval Patel

或者您可以使用output.replaceAll("[^A-Za-z0-9]", "")将所有非字母数字字符替换为空字符串。 - Dhaval Patel

1

s1CharSet.retainAll(s2CharSet);

似乎上面的那一行只是给出了交集(A 交 B)。

要获取所有唯一的字符，您需要获得UNION。A-B + A Intersection B + B-A。

更新：参考：交集和并集。

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

- sudhAnsu63

你说得对，但我不知道如何用代码实现？ - MMMMS

1

我会做类似以下的事情：

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

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

输出结果为：

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]

面试官可能会注意到几个小问题：

1) 在你的LinkedHashSet定义中使用了class而不是interface。这被广泛认为是一种不好的实践，可能被视为你对Java的熟悉程度有限 - 当然，这是否成为问题取决于他们所关心的经验水平。

2) 你的变量命名。如果候选人总是将对象命名为"thingy"或函数命名为"someFunction"，作为面试官你永远不会感到满意。一个天生的程序员会即兴产生有帮助的对象和函数名称。同样，这可能或可能不是一个问题，具体取决于他们所需要的经验水平。

3) 他们可能在寻找一些想象力来解释问题，例如询问空格是否是问题中的“字符”，或者对输出进行排序以使其更易读。或者询问如何处理I和i是否为相同的字符。

4) 他们可能期望你了解Java开发的时间线，例如说“这里我使用了Autoboxing，因此需要一个1.7或更高版本的编译器。”

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

- phil_20686

0

使用您的输入尝试此代码，您将获得所需的结果。

import java.util.HashSet;

  public class Practice {
        public static void main(String[] args) {
        String str1 = "Ro is Captain";
        String str2 = "Ri is keeper";

        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();`enter code here`

        HashSet hs = new HashSet();
        HashSet hf = new HashSet();
        HashSet hx = new HashSet();
        for (int i = 0; i < c1.length; i++) {
            hs.add(c1[i]);
        }
        for (int i = 0; i < c2.length; i++) {
            hs.add(c2[i]);
        }
        for (int i = 0; i < c1.length; i++) {
            hx.add(c1[i]);
        }
        for (int i = 0; i < c2.length; i++) {
            hf.add(c2[i]);
        }
        hx.retainAll(hf);
        hs.removeAll(hx);

        System.out.println("Uncommon Chars : " + hs);
    }
}

- Direactor

1

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Community

0

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

- Sourav Verma

0

打印出所有的公共字符：

public class Test10 {
    public static void main(String[] args) {
        String a = "Gini Gina Protijayi".toLowerCase();
        String b = "Soudipta".toLowerCase();
        // print out all the common characters
        a.chars()
        .distinct()
        .mapToObj(ch -> String.valueOf((char) ch))
        .filter(b::contains)
        .forEach(System.out::println);

    }// main
}

- Soudipta Dutta

0

假设为简单起见，我们的字符串仅由小写字符组成。现在，我们可以构造两个长度为26的数组，并计算字符出现的次数。现在比较这两个数组，如果两个数组都有计数> 0，则它们对两个字符串都是共同的。如果一个计数为零，另一个计数不为零，则它是特定字符串的唯一值。如果两者都为零，则该字符不存在于任何一个字符串中。

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

- Nitish Vashisth

0

这是我实现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;
    }
}

- user3530888

这看起来不错。我建议添加一个解决方案方法的简要概述。 - yakobom

谢谢。 (1) 仅有代码的答案很少有帮助。您可能需要解释一下，您认为这个代码比问题中的代码更好，并阐述如何更好。 (2) 我相信任务是要取两个字符串，但我在您的代码中只看到一个“abcabcxyz”？ - Ole V.V.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

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

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

Similar to your solution - populate two Set objects - one for each string, and then check the difference/common element between them by:
```
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.
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.