java - Java 中的字符串联合

Question

我被问到一个考试问题:

Write a program to read two string values, and find the intersection and union of entered string character sets. E.g.

• str1: "Hi hello"
• str2: "How are you"
• Union: "hielowaryu"
• Intersection: "hoe" (case insenstive)

这是一门 Java 101 类(class)，因此我们不应该使用任何超出绝对基础知识(没有高级数据结构)的内容。我无法在规定的时间内完成，但我想知道如何解决这个问题。

Answer 1

绝对最基本的方法:循环第一个字符串，检查第二个字符串是否包含它。看起来你的并集和相交不应该有重复项(如果可以的话，这是一个更难的问题)。

/** Returns the union of the two strings, case insensitive. 
    Takes O( (|S1| + |S2|) ^2 ) time. */
public static String union(String s1, String s2){
    String s = (s1 + s2).toLowerCase(); //start with entire contents of both strings
    int i = 0;
    while(i < s.length()){
        char c = s.charAt(i);
        if(i != s.lastIndexOf(c)) //If c occurs multiple times in s, remove first one
            s = s.substring(0, i) + s.substring(i+1, s.length());
        else i++; //otherwise move pointer forward
    }
}

/** Returns the intersection of the two strings, case insensitive. 
    Takes O( |S1| * |S2| ) time. */
public static String intersect(String s1, String s2){
    String s = "";
    s2 = s2.toLowerCase();
    for(char c : s1.toLowerCase().toCharArray()){
        if(s2.indexOf(c) != -1 && s.indexOf(c) == -1)
            s += c;
    }
    return s;
}