Word problem with same letters

Asked

Viewed 116 times

2

I’m solving a problem where I get one array of strings with different words, I have to find out for each word (string) which are your friends. Friendly words are those that have the same letters in different or equal order.

The problem is I have to return one array where each position has the words "friends".

Example:

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

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

To learn how you are friends I created the following method:

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

My idea was to walk the array and go building the array final, I’m just not getting a minimally efficient logic.

Any hint that might help me come up with a solution?

java array string algorithm

2 answers

2


Hello!

I made a reasonably efficient solution, it’s very easy to understand:

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

See working on Ideone

  • Any questions just ask. I hope I’ve helped!

  • Thanks for the help, I realized the logic missed only the part where words that have no friends should not enter the output array.

  • Oh yes, in your example "Asd" did not appear in the output. Nor had I seen it! Okay, I was going to modify the answer, but since you already posted, it’s a good thing there are two alternatives. If you prefer I upgrade mine to be right.

  • It is important to accept one of the answers, because then people can see that the question has already been answered! This is good both for those who consult the question later and for those who are looking for questions to answer. You can do this by clicking the right one below the answer score. More information here: http://meta.pt.stackoverflow.com/questions/1078/como-e-por-que-aceitar-uma-reply

1

Here is a solution:

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

}

Browser other questions tagged java array string algorithm

You are not signed in. Login or sign up in order to post.