Issue iterating through two arraylists

Question

EDIT: Thanks so much for all the really quick feedback. Wow. I did just paste it all for you instead of just those two for loops. Thanks.

This may have been totally answered before. I have read SO for the last few years but this is my first post. I have been using the site and others to help solve this so my apologies in advance if this has been answered!

I am iterating through two arraylists. One is derived from user input; the other is a dictionary file converted into an arraylist. I am trying to compare a word in the input with a dictionary word. The input list and the dictionary list are valid and if I simply iterate through them, they contain what they should (so that isn't the issue. I assume my issue is somewhere with how I am handling the iteration. I'm a fairly novice Java programmer so please go easy on me.

Thanks

    public String isSub(String x) throws FileNotFoundException, IOException  {
    //todo handle X
    String out = "**********\nFor input \n" + x + "If you're reading this no match was found.\n**********";
    String dictionary;


    boolean solve = true;

    /// Get dictionary
    dictMaker newDict = new dictMaker();
    dictionary = newDict.arrayMaker();

    List<String> myDict = new ArrayList<String>(Arrays.asList(dictionary.split(",")));
    List<String> input = new ArrayList<String>(Arrays.asList(x.split(" ")));
    List<String> results = new ArrayList<String>();
    //results = input;

    String currentWord;
    String match = "";
    String checker = "";
    String fail="";


    //Everything to break sub needs to happen here.
    while (solve) {


     for(int n = 0; n < input.size(); n++) { //outside FOR (INPUT)
       if(!fail.equals("")) results.add(fail);
       checker = input.get(n).trim();
       for(int i = 0; i < myDict.size(); i++) { //inside FOR (dictionary)
        currentWord = myDict.get(i).trim();
        System.out.print(checker + " " + currentWord + "\n");
        if(checker.equals(currentWord)) {

                match = currentWord;
                results.add(currentWord);
                fail="";

            } //end if
            else {

                fail = "No match for " + checker;

            }

          }//end inside FOR (dictionary)

        }   //END OUTSIDE FOR (input)

        solve=false;

     } //end while


        out = results.toString();

        return out;
}

Output results for input "test tester asdasdfasdlfk" [test, No match for test, tester, No match for tester]

Answer 1

You should place the dictionary to a HashSet and trim while add all words. Next you just need to loop the input list and compare with dict.conatins(inputWord). This saves the possible huge dictionary loop processed for all input words.

Untested brain dump:

HashSet<String> dictionary = readDictionaryFiles(...);
List<String> input = getInput();

for (String inputString : input)
{
     if (dictionary.contains(inputString.trim()))
     {
          result.add(inputString);
     }
}

out = result.toString()
....

And a solution similar to the original posting. The unnecessary loop index variables are removed:

    for (String checker : input)
    { // outside FOR (INPUT)
        fail = "No match for " + checker;
        for (String currentWord : myDict)
        { // inside FOR (dictionary)
            System.out.print(checker + " " + currentWord + "\n");
            if (checker.equals(currentWord))
            {
                match = currentWord;
                results.add(currentWord);
                fail = null;
                break;
            }
        } // end inside FOR (dictionary)
        if (fail != null)
        {
            results.add(fail);
        }
    } // end outside FOR (input)

    solve = false;

    return results.toString();

The trim should be made while add the elements to the list. Trim the dictionary values each time is overhead. And the inner loop itself too. The complexity of the task can be reduced if the dictionary data structure is changed from List to Set.

Adding the result of "fail" is moved to the end of the outer loop. Otherwise the result of the last input string is not added to the result list.

The following code is terrible:

else {
    fail = "No match for " + checker;
}

The checker does not change within the dictionary loop. But the fail string is constructed each time the checker and the dictionary value does not match.

Answer 2

If you are using a dictionary, you should get it with keys not with index. So it should be

                if(myDict.containsKey(checker)){
                    String currentWord =myDict.get(checker);
                    System.out.print(checker + " " + currentWord + "\n");
                    match = currentWord;
                    results.add(currentWord);
                    fail = "";
                }
                else {
                    fail = "No match for " + checker;
                }

I think more or less your code should like following.

ArrayList<String> input= new ArrayList<String>();
      input.add("ahmet");
      input.add("mehmet");
      ArrayList<String> results= new ArrayList<String>();
      Map<String, String> myDict = new HashMap<String, String>();
      myDict.put("key", "ahmet");
      myDict.put("key2", "mehmet");
      String match="";
      String fail="";
    for (int n = 0; n < input.size(); n++) { //outside FOR (INPUT)
            if (!fail.equals("")) 
                results.add(fail);
            String checker = input.get(n).trim();

            for (int i = 0; i < myDict.size(); i++) { //inside FOR (dictionary)

             //   String currentWord = myDict.get(i).trim();
                if(myDict.containsKey(checker)){
                    String currentWord =myDict.get(checker);
                    System.out.print(checker + " " + currentWord + "\n");
                    match = currentWord;
                    results.add(currentWord);
                    fail = "";
                }
                else {
                    fail = "No match for " + checker;
                }
            } // end inside FOR (dictionary)
        }   // end outside FOR (input)

     //   solve = false; I dont know what is this

    //} //end while. no while in my code

    return results.toString();

Answer 3

Carl Manaster gave the correct explanation.

Here's an improved version of your code:

for (int n = 0; n < input.size(); n++) { //outside FOR (INPUT)
    String checker = input.get(n).trim();
    boolean match = false;
    for (int i = 0; i < myDict.size(); i++) { //inside FOR (dictionary)
        String currentWord = myDict.get(i).trim();
        System.out.print(checker + " " + currentWord + "\n");
        if (checker.equals(currentWord)) {
            match = true;
            results.add(currentWord);
            break;
        } //end if
    } //end inside FOR (dictionary)
    if (!match) {
        results.add("No match for " + checker);
    }
} //END OUTSIDE FOR (input)

Also, consider using a HashMap instead of an ArrayList to store the dictionary and trim the words when you store them to avoid doing it in each pass.

Answer 4

It looks as though every word in input gets compared to every word in your dictionary. So for every word that doesn't match, you get a fail (although you only write the last failure in the dictionary to the results). The problem appears to be that you keep looping even after you have found the word. To avoid this, you probably want to add break to the success case:

if (checker.equals(currentWord)) {
    match = currentWord;
    results.add(currentWord);
    fail = "";
    break;
} else {
    fail = "No match for " + checker;
}