2

Estou a resolver um problema onde recebo um array de strings com diferentes palavras, tenho que descobrir para cada palavra (string) quais são as suas amigas. Palavras amigas são aquelas que têm as mesmas letras em diferentes ou igual ordem.

O problema é que tenho que retornar um array em que cada posição tenha as palavras "amigas".

Exemplo:

Input: {"ola", "lao", "aol", "asd", "asdf", "fdsa"}

Output: {"ola lao aol", "asdf fdsa"}

Para saber como são amigas criei o seguinte método:

static boolean sameChars( String firstStr , String secondStr ) {
    char[ ] first  = firstStr.toCharArray( );
    char[ ] second = secondStr.toCharArray( );
    Arrays.sort( first );
    Arrays.sort( second );

    return Arrays.equals( first , second );
}

Minha ideia era percorrer o array inicial e ir construindo o array final, só não estou a conseguir uma lógica minimamente eficiente.

Alguma dica que me possa ajudar a chegar a solução?

2 Respostas 2

2

Olá!

Fiz uma solução razoavelmente eficiente, está bem fácil de entender:

import java.util.*;

public class App {

    public static void main(String[] args) {

        String a[] = {"ola","lao","aol","asd","asdf","fdsa"};       
        List<Integer> lista = new ArrayList<Integer>(Collections.nCopies(a.length, 0));

        int num=1;
        for(int i=0; i<a.length; i++){
            if(lista.get(i)==0){
                lista.set(i, num);
                for(int j=i+1; j<a.length; j++)
                    if( lista.get(j)==0 && sameChars(a[i], a[j]))
                        lista.set(j, num);
                num++;
            }
        }

        num--;
        StringBuilder sb[] = new StringBuilder[num];
        for(int i=0; i<num; i++)
            sb[i] = new StringBuilder();


        for(int i=0; i<lista.size(); i++){
            sb[lista.get(i)-1].append(a[i]);
            sb[lista.get(i)-1].append(" ");
        }

        String[] str = new String[sb.length];
        int i=0;
        for(StringBuilder s : sb)
            str[i++] = s.deleteCharAt(s.length()-1).toString();

        imprime(str);
    }


    static boolean sameChars( String firstStr , String secondStr ) {
        char[ ] first  = firstStr.toCharArray( );
        char[ ] second = secondStr.toCharArray( );
        Arrays.sort( first );
        Arrays.sort( second );
        return Arrays.equals( first , second );
    }

    static void imprime(String[] sb) {
        int num = sb.length;
        System.out.print("{");
        for(int i=0; i < num; i++){
            System.out.print("\""+sb[i]+"\"");
            if(i!=num-1)
                System.out.print(", ");
        }
        System.out.print("}");
    }
}

Veja funcionando no Ideone

4
  • Qualquer dúvida é só perguntar. Espero ter ajudado! Commented 3/08/2016 às 14:30
  • Obrigado pela ajuda, percebi a logica faltou só a parte em que palavras que não têm amigas não devem entrar no array de output. Commented 4/08/2016 às 11:19
  • Ah sim, no seu exemplo o "asd" não apareceu no output. Nem tinha visto isso! Ok, eu iria modificar a resposta, mas já que você já postou é até bom que ficam as duas alternativas. Se você preferir eu atualizo a minha para ficar certo. Commented 4/08/2016 às 13:52
  • É importante aceitar uma das respostas, pois assim as pessoas podem ver que a pergunta já foi respondida! Isso é bom tanto para quem for consultar a pergunta depois quanto para quem estiver procurando perguntas para responder. Você pode fazer isso clicando no certo abaixo da pontuação da resposta. Mais informações aqui: meta.pt.stackoverflow.com/questions/1078/… Commented 4/08/2016 às 13:55
1

Aqui fica uma solução:

static String[ ] solution( String[ ] input ) {
    //Solution
    List<Integer> lista = new ArrayList<Integer>( Collections.nCopies( input.length , 0 ) );
    int num = 1;
    boolean _check = false;
    for( int i = 0 ; i < input.length ; i++ ) {
        if( lista.get( i ) == 0 ) {
            lista.set( i , num );
            for( int j = i+1 ; j < input.length ; j++ )
                if( lista.get( j ) == 0 && sameChars( input[ i ] , input[ j ] ) ) {
                    lista.set( j , num );
                    _check = true;
                }

            if( !_check ) 
                lista.set( i , -1 );
            else
                num++;
            _check = false;
        }
    }

    num--;
    StringBuilder sb[ ] = new StringBuilder[ num ];
    for( int i=0 ; i < num ; i++ )
        sb[ i ] = new StringBuilder( );



    for( int i=0 ; i < lista.size( ) ; i++ ) {
        if( lista.get( i ) >= 0 ) {
            sb[ lista.get( i ) - 1 ].append( input[ i ] );
            sb[ lista.get( i ) - 1 ].append(" ");
        }
    }

    String[] str = new String[sb.length];
    int i=0;
    for(StringBuilder s : sb)
        str[i++] = s.deleteCharAt(s.length()-1).toString();


    return str;

}

static boolean sameChars( String firstStr , String secondStr ) {
      char[ ] first  = firstStr.toCharArray( );
      char[ ] second = secondStr.toCharArray( );
      Arrays.sort( first );
      Arrays.sort( second );
      return Arrays.equals( first , second );
}

public static void main( String[ ] args ) {

    String[ ] myStringArray = {"ola","lao","aol","asd","asdf","fdsa"};
    String[ ] output = solution( myStringArray );
    System.out.println( "Solução => " );
    for( int i = 0 ; i < output.length ; i++ ) {
        System.out.println( output[ i ] );
    }

}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .