Short C++ DFS+MEMORIZATION 26ms


  • 2
    B
    class Solution {
        int numRepetition(string &s, string &t) {
            int cnt=0,i=0;
            while(i<s.length()) {
                if(s.substr(i,t.length())!=t) break;
                cnt++;
                i+=t.length();
            }
            return cnt;
        }
        string dfs(string s, unordered_map<string,string> &m) {
            if(s.length()<5) return s;
            if(m.count(s)) return m[s];
            string res = s;
            for(int i=0;i<s.length();i++) {
                string s1 = s.substr(0,i+1);
                int cnt = numRepetition(s,s1);
                string t;
                for(int k=1;k<=cnt;k++) {
                    if(k==1) t=s1+dfs(s.substr(i+1),m);
                    else t = to_string(k)+"["+dfs(s1,m)+"]"+dfs(s.substr(k*s1.length()),m);
                    if(t.length()<res.length()) res=t;            
                }
            }
            m[s]=res;
            return res;        
        }
    public:
        string encode(string s) {
            unordered_map<string,string> m;
            return dfs(s,m);
        }
    };
    

Log in to reply
 

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