Come stampare un alfabeto unico da due stringhe usando Java?

Question

Recentemente, ho partecipato a un'intervista. Mi hanno chiesto di scrivere un programma per stampare alfabeti unici e caratteri comuni da due stringhe. Ho scritto il codice qui sotto per stampare i caratteri comuni:

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

ma hanno detto come non sono soddisfatto della mia risposta. Immagino sia perché non si aspettano lo retainAll. Quindi, per favore dimmi il modo giusto di programmare per soddisfarli in futuro.

Persino su Google ma non ho trovato collegamenti validi e comprensibili.

Quindi, come stampare caratteri univoci e comuni da due stringhe senza utilizzare retainAll?

Qualsiasi codice sarebbe apprezzato.

Answer 1

È possibile che l'intervistatore volesse verificare la comprensione degli interni di come risolvere questo problema in modo efficiente e l'utilizzo di retainAll() non rispetta lo scopo di questa attività.

per la sua attuazione "da zero" si può utilizzare diversi approcci:

1. Simile alla soluzione - aumento di popolazione due Set oggetti - uno per ogni corda, e quindi controllare l'elemento di differenza/comune tra loro da :

   for (Character c : set1) { 
       if (set2.contains(c)) { 
        System.out.println(c); 
       } 
   } 
   

   si può anche usare un bitset se l'alfabeto è conosciuto per essere costante (e abbastanza piccolo), altrimenti un HashSet va bene e raggiungerà O(n) performance media caso.

2. ordinamento e iterazione: ordina i due array di caratteri e scorre insieme per trovare caratteri comuni (e univoci). Mentre in Java non c'è alcun beneficio reale (poiché String è immutabile, quindi è necessario creare un nuovo char[]) in altre lingue, consente di risparmiare spazio e può essere fatto all'interno con davvero poco spazio aggiuntivo.

Answer 2

Stampa caratteri univoci e comuni da due stringhe senza utilizzare 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(" ", ""); 

Risultati:

Common:danli 
Unique:gvmIfebcoutsry 

Answer 3

s1CharSet.retainAll (s2CharSet);

Sembra che la riga sopra abbia appena dato il numero intersection (A intersection B).

Per ottenere tutti i caratteri Unique necessari per ottenere l'UNION. A-B + A intersezione B + B-A.

UPDATE: Riferimento: 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; 
} 
    } 

Answer 4

avrei fatto qualcosa di simile:

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

Questo fondamentalmente solo sfrutta il comportamento del set aggiungere funzioni, che restituisca true se l'elemento è stato non nel set, e falso se lo fosse. Il set evita la duplicazione.

Dà l'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] 

Ci sono un paio di piccoli punti che un intervistatore potrebbe salire su:

1) è stato utilizzato il codice categoria e non l'interfaccia nelle definizioni LinkedHashSet. Questo è ampiamente considerato come una cattiva pratica e potrebbe essere considerato come una dimostrazione di una scarsa familiarità con Java-ofc, sia che si tratti di un problema a seconda del livello di esperienza a cui sono interessati.

2) La denominazione delle variabili. Non sei mai felice come intervistatore se il tuo candidato continua a nominare oggetti "thingy" o funzioni "someFunction", un programmatore naturale produce al volo nomi utili per oggetti e funzioni. Di nuovo, a seconda del livello di esperienza che volevano, questo potrebbe o potrebbe non essere un problema.

3) Potrebbero aver cercato un po 'di immaginazione nell'interpretazione della domanda, ad es. per chiedere se lo spazio bianco fosse un "carattere" nella domanda o per ordinare l'output per renderlo più leggibile. O per chiedere se trattare io e io come gli stessi o diversi personaggi.

4) Avrebbero potuto aspettarsi una certa conoscenza della timeline dello sviluppo Java, ad es. per dire "Qui ho usato Autoboxing, quindi richiede un compilatore 1.7 o successivo."

5) Potresti aver impiegato troppo tempo o avere bisogno di troppi suggerimenti/correzioni sulla sintassi.

Answer 5

quando si sta per un colloquio e se chiedono domande sciocche come quella che hai detto, allora non sono alla ricerca di una struttura di raccolta complessa. Stanno cercando se si può fare lo stesso a livello di root con le proprie capacità di codifica, tenendo presente come si scrive un codice che sarà in grado di gestire i casi anche se i dati forniti andranno a milioni.

Questo problema può essere facilmente risolto prendendo un byte []. Sappiamo che il char è rappresentato dal numerico internamente.

così nella prima iterazione, basta iterare i caratteri della prima stringa (str1) e impostare la posizione di byte in una certa costante, ad esempio 1.

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

così nella seconda iterazione, basta iterare i caratteri della seconda stringa e impostano la posizione dei byte su qualche costante dire 2 solo se è impostata su 1 e 3 per rappresentare che è unica per str2.

Nella terza iterazione, basta scorrere il byte arr e stampare i caratteri (convertire l'indice in carattere) dove mai è 2 per comune e 1/3 per unico.

soluzione finale O (n) e scalabile.

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

Answer 7

Questa è la mia soluzione che implementa LinkedHashSet per mantenere l'ordine dei caratteri nelle stringhe.

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

Answer 8

Lasciamo dire per semplicità che le nostre stringhe sono composte solo da caratteri minuscoli. Ora possiamo costruire due array di lunghezza 26 e contare l'occorrenza dei caratteri. Ora confronta entrambi gli array, se entrambi hanno un conteggio> 0, quindi è comune a entrambe le stringhe. Se il conteggio è zero in uno e non zero in altri, è unico per quella particolare stringa. Se entrambi zero, il carattere non è presente in nessuna delle due stringhe.

L'approccio sopra riportato potrebbe essere utilizzato per molti problemi simili.