Accepted O(N^3) with Pruning


  • 0
    C

    Hey, I tried this problem and got TLE (I was using O(N^3) algo), then I tweaked my inner loop to do some pruning, as follows:

    class Solution {
    public:
        string longestPalindrome(string s) {
            int len = s.length();
            string ret;
            int maxlen = 0;
            for(int i = 0;i<len;i++){
                for(int j = len-1;j>=i;j--){
                    // If the length of longest current result is longer than what is to be checked, skip it.
                     
                    if(maxlen > j-i+1)continue;
                    int temp_i,temp_j;
                    temp_i = i;
                    temp_j = j;
                    bool valid = true;
                    while(temp_i < temp_j){
                        if(s[temp_i] != s[temp_j]){
                            valid = false;
                            break;
                        }
                        temp_i++;
                        temp_j--;
                    }
                    if(valid){
                        if(maxlen < j-i+1){
                            maxlen = j-i+1;
                            ret = s.substr(i,maxlen);
                        }
                    }
                }
            }
            return ret;
        }
    };
    

    IMO my solution shouldn't be allowed to pass and you can consider adding test cases to account for this kind of solutions!

    Good day! :)


Log in to reply
 

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