TopCoder grafixCorrupt.selectWord solution


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: TopCoder grafixCorrupt.selectWord solution

  1. #1
    Join Date
    Sep 2004
    Posts
    2

    TopCoder grafixCorrupt.selectWord solution

    Here's my solution to grafixCorrupt.selectWord:

    Code:
        public int selectWord(String[] dictionary, String candidate)
        {
            int retval = -1;
            int[] scores = new int[dictionary.length];
            int iBestScore;
            // scan through each entry in dictionary, computing its score and assinging it to its
            // corresponding place in scores.
            int iThisScore = 0;
            for (int i=0; i<dictionary.length; i++)
            {
                // compute its score.
                iThisScore = 0;
                for (int iChar=0; iChar<candidate.length(); iChar++)
                {
                    if (dictionary[i].charAt(iChar) == candidate.charAt(iChar))
                    {
                        iThisScore++;
                    }
                }
                // add the score to scores[].  Couple the score with the index; later when I sort
                // the scores, I won't lose the corresponding indexes.  In case of a tie, I have 
                // to pick the word that occurs first.  When I sort, I'm going to pick the last 
                // word; if the last is a tie, it'll pick the last-occurring high score.  So 
                // instead of using the index per se, I'll be using its length from the beginning.  
                scores[i] = (iThisScore * 100) + (dictionary.length - i);
            }
            
            Arrays.sort(scores);       
            iBestScore = dictionary.length - (scores[scores.length-1] % 100);  // convert back to the index
            retval = (iBestScore == 0) ? -1 : iBestScore;
            return retval;
        }

    Comments, critiques, suggestions, anyone?

    Regards,
    Brismith

  2. #2
    Join Date
    Oct 2004
    Location
    London
    Posts
    1

    a comment

    If you keep a record of what the best score is so far (and the index of that score) as you loop through the dictionary, then you don't need to do the sorting stuff at the end and you don't need an array of scores.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center