C++ O(NlgN) algorithm and O(N) algorithm


  • 0
    T

    O(NlgN) algorithm, using sort and then compare character by character.

    class Solution {
    public:
        char findTheDifference(string s, string t) {
            int i = 0;
            sort(s.begin(), s.end());
            sort(t.begin(), t.end());
            for (i = 0; i < s.size(); ++i) {
                if (s[i] != t[i])
                    break;
            }
            
            return t[i];
        }
    };
    

    O(N) algorithm using XOR

    class Solution {
    public:
        char findTheDifference(string s, string t) {
            char r = 0;
            for(auto c : s)
                r ^= c;
            
            for (auto c : t)
                r ^= c;
    
            return r;
        }
    };
    

Log in to reply
 

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