Recursive Java solution with memoization, 45 msecs


  • 2
    F
    static Map<String, String> prevResults = new HashMap<>();
    public String encode(String s) {
        if (s == null || s.length() < 5) {
            return s;
        }
        if (prevResults.containsKey(s)) {
            return prevResults.get(s);
        }
        int strlen = s.length();
        int minLength = Integer.MAX_VALUE;
        String choosenString = s;
        for (int i = 1; i < s.length() / 2 + 1; i++) {
            String encodedString = s;
            // split the string at index i into 2 strings
            String leftStr = s.substring(0, i);
            String rightStr = s.substring(i, strlen);
            int repeatCounter = findPrefixRepetitions(leftStr, rightStr);
            if (repeatCounter > 0) {
                encodedString = "" + (repeatCounter + 1) + '[' + encode(leftStr) + ']' + encode(rightStr.substring(repeatCounter * leftStr.length()));
            }
            String encodedString2 = encode(leftStr) + encode(rightStr);
            if (encodedString2.length() < encodedString.length()) {
                encodedString = encodedString2;
            }
            if (encodedString.length() < strlen) { 
                if (minLength > encodedString.length()) {
                    choosenString = encodedString;
                    minLength = encodedString.length();
                }
            }
        }
        prevResults.put(s, choosenString);
        return choosenString;
    }
    
    private int findPrefixRepetitions(String prefix, String str) {
        int repeatCounter = 0;
        int startIndex = 0;
        do {
            int prefixIndex = str.indexOf(prefix, startIndex);
            if (prefixIndex != startIndex) {
                break;
            }
            repeatCounter++;
            startIndex = prefixIndex + prefix.length();
        } while (startIndex < str.length());
        return repeatCounter;
    }
    

    This solution's complexity is not clear to me (suspected to be exponential) but it passes all tests. It uses recursion with memoization instead of dynamic programming and surprisingly beats in time many dynamic programming solutions.


  • 0

    Nice solution, clear and neat code and runs very fast. I think the time complexity should be O(n^4), where n is the length of s. The outer loop plus find prefix contributes n^2, while the mem map will store up to all potential substrings of s, which contributes n^2, so the final time complexity should be O(n^4)


Log in to reply
 

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