Is there a easy way to find a word with a given String?

Question

I'm having some problems in my application.

Basically, I need to read some string from the user (they'll type an amount of letters mixed), and my job is to find a word that I can make using some letters they gave me.

Here's an example:

User types "emmfosor". Thinking fast, I can make 2 words out of it: 'some' and 'from', but the letters of these words are mixed.

However, to make my job easier, I have a database of words. It's on a txt file like this:

apple
strawberry
boring
buildings
book
superior
bathroom

Every solution that I make is wrong, or the words just don't appear. Can somebody help me?

Answer 1

This is not the efficient way to do this. For huge word database it's not suitable. But we could try something like this.
For each character in input, remove the character from all words in the words list. At the end the word list will have 0 length strings which are match.
Following is my basic implementation of this. You can use StringBuilder, Maps, removing duplicate chars from input etc. to improve performance.

public class Test {

   public static void main(String[] args) throws Exception {
       String[] data = {"some", "zoo", "from"};
       String input = "emmfosor";
       System.out.println("input: " + input);
       System.out.println("possible words: "+getMatched(input, data));
    }
   
   public static List<String> getMatched(String input, String[] data){
       List<String> result = new ArrayList<>();
       //make a copy to work on
       String[] copy = Arrays.copyOf(data, data.length);
       char[] chars = input.toCharArray();
       for(char c : chars) {
           for (int i = 0; i < copy.length; i++) {
            String word = copy[i];
            if(!word.isBlank())
                copy[i] = word.replaceAll(Character.toString(c), "");
        }
       }
       for (int i = 0; i < copy.length; i++)
         if(copy[i].isBlank())     //find empty strings
             result.add(data[i]);
           return result;
   }
}

Output:

input: emmfosor
possible words: [some, from]

Modify the code as per your needs.

Answer 2

If you are sure that the input contains a single word, then there is an easy linear trick.

1. Define a method for sorting letters inside a string. The String is immutable, so the method will return a new object, obviously:

public static String sortString(String inputString){
    char tempArray[] = inputString.toCharArray();
    Arrays.sort(tempArray);
    return new String(tempArray);
}

2. Sort the letters of all the strings from your file and put them into a map:

Map<String, String> map = Files.lines(Paths.get("filename"))
                               .collect(Collectors.toMap(s -> sortString(s), s -> s));

3. Now, once you have everything prepared, you can accept the input:

String inputString = // read it somehow

String outputString = map.get(sortString(inputString));

Answer 3

Well, you first have to find a way to get the contents of that .txt file, and put it in some kind of array. Here is my best method to make that:

class ParseText extends File {
  private Scanner readSelf;
  private String content;

  public ParseText(String filename) {
    super(filename);
    readSelf = new Scanner(this);
    while(readSelf.hasNextLine()) {
      content += readSelf.nextLine();
    }
    readSelf.close();
  }

  public String[] getEntries() {
    ArrayList<String> entries;
    while(true) {
      int firstBreak = content.indexOf('\n');
      boolean notLast = (firstBreak != -1);
      // ternary operator
      entries.add(content.substring(0, notLast ? (firstBreak - 1) : content.length() - 1));

      //more ternary operators
      content = notLast ? (content.substring(firstBreak + 1)) : "";
      if(content.length() == 0) {break};
    }
    return entries.toArray(new String[0]); 
  }

  public static HashMap<char, int> getCharacterHashMap(String string) {
    HashMap<char, int> charHash = new HashMap<char, int>();

    for(char c : string.toCharArray()) {
      if(charHash.containsKey(c)) {
        int old = charHash.get(c);
        charHash.replace(c, old, old + 1);
      }
      else {
        charHash.put(c, 1);
      }
    }

    return charHash;
  }
}

Next, an algorithm. We should start to use hashmaps here, since we want to make an un-scrambler for Strings. Each HashMap object should have characters as keys, and integers as values.

class Unscramble {
  private static String[] entries = new ParseText("entries.txt").getEntries();
  
  public static match(String someGibberish) {
    Object gibberishHash = ParseText.getCharacterHashMap(someGibberish);
    ArrayList<int> passes = new ArrayList<int>();
    for(int i = 0; i < entries.length; i++) {
      
      HashMap<char, int> currentHash = ParseText.getCharacterHashMap(entries[i]);
      char[] keyArray = currentHash.keySet().toArray();
      boolean[] fits = new boolean[keyArray.length];
      for(int j = 0; j < keyArray.length; i++) {
        if(gibberishHash.get(keyArray[j]) != null && currentHash.get(keyArray[j]) <= gibberishHash.get) {
          fits[j] = true
        }
        else {
          //breaking to speed up running
          break;
        }
      }

      boolean passesEntry = true;
      for(int k = 0; k < fits.length; i++) {
        if(!(fits[k])) {
          passesEntry = false;
          break;
        }
      }

      if(passesEntry) {
        passes.add(i);
      }
    }
  }
}

I haven't tested this for any errors, so just comment to inform me of any errors. You might also be able to speed this up more with threads, but this should be enough.