Solution works, however doesn't pass the time-limit exceed. Suggestions?


  • 0
    B

    My solution works with the basic input. I also checked the long array on the IDE and that works too.
    What could be wrong? If the time it takes to process is too long, how can I improve this without using bitwise manipulation (to me bit-wise is not very readable code)?

    public static int maxProduct(String[] words) {
            
            int indexOfFirst;
            int indexOfSecond;
            int currentMaxProduct = 0;
            
            for(int i = 0; i < words.length; i++)
            {
               String[] arrayLetters = words[i].split("(?!^)");
               
                 for(int j = i; j < words.length; j++) // check next words
                 {
                       for(int z = 0; z < arrayLetters.length; z++) //common letter finder
                       {
                           String currentLetter = arrayLetters[z];
                           
                           if(words[j].indexOf(currentLetter) < 0)
                           {
                               if(z == (arrayLetters.length-1))
                               {
                                   int firstLength = words[i].length();
                                   int secondLength = words[j].length();
                                   
                                   int value = firstLength * secondLength;
                                   if(value > currentMaxProduct)
                                   {
                                       currentMaxProduct = value;
                                   }
                               }
                           }
                           else
                           {
                               z = arrayLetters.length;
                           }
                       }
                 }
            }
            
            return currentMaxProduct;
        }

  • 0
    V
    In the second loop, j can begin from i+1,i.e.for(int j = i+1; j < words.length; j++).
    It is meaningless to compare words[i] and words[i].But i think it still couldn't pass
    could you understand this:https://leetcode.com/discuss/92140/share-my-c-solution-with-explanation-easy-to-understand

  • 0
    V

    Your algorithm run time is O(n^2 * m) where n is the number of words and m is the average length of word in words array. Using bitwise operations you can reduce the complexity to O(n^2) because the bit operations is O(1). Instead of using bitwise operation, you can also use HashMap or a char array of alphabet size(26). This also is treated as O(1). So you need to preprocess and store the char array for every word. When you do the maxProduct computation you can reduce the O(m) in that to O(1) by comparing the char array of the words. The run time would be O(n^2) and space would be O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.