4ms C++ solution


  • 1
    Y
    class Solution {
    public:
        // util function to determine if 2 string are in the same pattern
        bool isSamePattern(const string& s1, const string& s2) {
            if (s1.size() != s2.size()) {
                return false;
            }
            
            if (s1.size() == 1) {
                return true;
            }
            
            for (int i = 0; i < s1.size(); i++) {
                for (int j = i+1; j < s1.size(); j++) {
                    int delta1 = s1[j] - s1[i];
                    int delta2 = s2[j] - s2[i];
                    // get "abs" value
                    if (delta1 < 0) delta1 = 26 + delta1;
                    if (delta2 < 0) delta2 = 26 + delta2;
                    if (delta1 != delta2) {
                        return false;
                    }
                }
            }
            return true;
        }
        
        vector<vector<string>> groupStrings(vector<string>& strings) {
            vector<vector<string>> ret;
            for (string s : strings) {
                bool flag = false;
                // query all existing strings
                for (int i = 0; i < ret.size(); i++) {
                    if (isSamePattern(s, ret[i][0])) {
                        // found
                        ret[i].push_back(s);
                        flag = true;
                        std::sort(ret[i].begin(), ret[i].end());
                        break;
                    }
                }
                if (!flag) {
                    // not found
                    vector<string> newPattern = { s };
                    ret.push_back(newPattern);
                }
            }
            return ret;
        }
    };

  • 0
    K

    The answer is nice. The isSamePattern can be further simplified as:

    bool isSame(string& s, string& t)
    {
        if(s.size()!=t.size()) return false;
        if(s.size()==1) return true;
        int dist = (t[0]-s[0]<0)? 26+(t[0]-s[0]) : t[0]-s[0];
        for(int i = 1; i<s.size(); ++i)
        {
            int a = (t[i]-s[i]<0)? 26+(t[i]-s[i]) : t[i]-s[i];
            if(a!=dist) return false;
        }
        return true;
    }

Log in to reply
 

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