compare scrambled words with an unscrambled wordlist php

Question

Hi,

i search a method to compare scrambled words with a wordlist full of unscrambled words for example:

the scrambled word is "lonbayb" and somewhere in the wordlist is the word "babylon". the script should show me the unscrambled word

any idea how to solve this problem?

Answer 1

A simple solution that comes to mind is to sort the letters in both the scrambled and unscrambled words, alphabetically, before comparing. I'll call this "shuffling":

"babylon" ==> "abblnoy"

In practical terms, you should create a second wordlist from your reference wordlist, with the reference wordlist having its entries shuffled like this.

and then when you're looking at a new word and want to know if it's in the list, shuffle that the same way and you can do a simple search in your shuffled reference list. If you sort words in the shuffled reference list alphabetically, you can even do a binary search on it. Or you put the shuffled reference words into a hashset or a b-tree... whatever is easy to quickly search in.

Answer 2

To shuffle the words use str_shuffle(). To compare a shuffled string to a wordlist, you can use count_chars().

class WordFinder
{
    protected $_wordList;
    protected $_map;

    public function __construct(array $wordList)
    {
        $this->_wordList = $wordList;
    }

    protected function _initMap()
    {
        if(!is_array($this->_map)) {
            $this->_map = array();
            foreach($this->_wordList as $word) {
                $key = count_chars($word, 3);
                if(!isset($this->_map[$key])) {
                    $this->_map[$key] = array();
                }
                $this->_map[$key][] = $word;
            }
        }
    }

    public function findWords($searchWord)
    {
        $searchWord = count_chars($searchWord, 3);
        $this->_initMap();
        if(isset($this->_map[$searchWord])) {
            return $this->_map[$searchWord];
        }
        return false;
    }    
}

Then do

$list   = array('evil', 'live', 'vile', 'cat');
$finder = new WordFinder($list);
var_dump($finder->findWords('evli'));

And this will return

array(3) {
  [0]=>
  string(4) "evil"
  [1]=>
  string(4) "live"
  [2]=>
  string(4) "vile"
}

EDIT I've exchanged the original code with this version, as it performs much better with large wordlists. I've tested the above on my 2,2 Ghz Dual Core and it would finish 10000 calls to findWords() in a collection of 10000 words in a mere 0.08 seconds. The other version would take 207 seconds. See the revision for the old version.