3 ms Java Recursive clean code


  • 2
    I
        public String findContestMatch(int n) {
            StringBuilder sb = new StringBuilder();
            helper(sb, 3, n, 1);
            return sb.toString();
        }
    
        void helper(StringBuilder sb, int sum, int n, int val) {
            if (sum > n + 1) {
                sb.append(val);
                return;
            }
            sb.append('(');
            helper(sb, (sum << 1) - 1, n, val);
            sb.append(',');
            helper(sb, (sum << 1) - 1, n, sum - val);
            sb.append(')');        
        }
    

  • 0

    The basic idea is to build a tree, for the case of n = 8, the tree is like this:

    I had the similar idea and below is my code:

    public class Solution {
        public String findContestMatch(int n) {
            TreeNode[] matches = new TreeNode[n];
            for (int i = 0; i < n; i++) {
                matches[i] = new TreeNode(i + 1);
            }
            int len = n;
            while (len > 1) {
                for (int i = 0; i < len / 2; i++) {
                    TreeNode newNode = new TreeNode(matches[i].val);
                    newNode.left = matches[i];
                    newNode.right = matches[len - 1 - i];
                    matches[i] = newNode;
                }
                len = len >> 1;
            }
            StringBuilder sb = new StringBuilder();
            dfs(matches[0], sb);
            return sb.toString();
        }
    
        void dfs(TreeNode root, StringBuilder sb) {
            if (root.left == null && root.right == null) {
                sb.append(root.val);
                return;
            }
            sb.append("(");
            dfs(root.left, sb);
            sb.append(",");
            dfs(root.right, sb);
            sb.append(")");
        }
    }
    

    It's verbose but easier to understand: just build the tree by grouping matches one round at a time, then do a DFS to get the output string.

    My solution's complexity:

    • for building the tree: 2N space and 2N time.
    • for DFS: 2N time.

    While his solutions uses 2N time and O(1) space. It's also much conciser than mine.

    I tried to submit his solution, got a 4ms (99%) while my own solution is 6ms (98%) (2017-07-20 16:58:23);

    I still decided to share my version since mine is easier to understand and come up with step by step. But again I definitely think his is better.


Log in to reply
 

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