Construct Smallest Number From DI String

Week of backtracking!

My initial solution was quite brute-force, just recursively iterating through all the minimum values, until we stumble upon a solution.

code

class Solution {
public:
    bool recursion(int index, string pattern, string& ans, int *num) {
        if (index == pattern.size()+1) {
            return true;
        }
        for (int i = 1; i < 10; ++i) {
            if (num[i] == 1) continue;
            if (index > 0 and (pattern[index-1] == 'I' ? ans[ans.size()-1]-'0' > i : ans[ans.size()-1]-'0' < i)) continue;

            num[i] = 1;
            ans += char(i+'0');
            if (recursion(index+1, pattern, ans, num)) {
                return true;
            }

            ans.pop_back();
            num[i] = 0;
        }
        return false;
    }
    string smallestNumber(string pattern) {
        int num[10] = {0};
        string ans = "";
        recursion(0, pattern, ans, num);
        return ans;
    }
};

complexity

• Time: O(n)
• Space: O(n)

I realised that there was a much simpler intuitive way of writing the solution.

• for pattern[i] == 'I', we can just add the smallest consequent number
• for pattern[i] == 'D', we can just keep a counter of the number of D values we stumble upon, and then "bulk-add" the numbers in descending order once pattern[i] != 'D'

code

class Solution {
public:
    string smallestNumber(string pattern) {
        string ans = "";
        for (int i = 0; i <= pattern.size(); ++i) {
            int num = i+1;
            while (pattern[i] == 'I') {
                ans += num++ +'0';
                ++i;
            }
            int counter = 0;
            while (pattern[i] == 'D') {
                ++counter;
                ++i;
                ++num;
            }
            ++counter;
            while (counter--) {
                ans += num-- +'0';
            }
        }
        return ans;
    }
};

complexity

• Time: O(n)
• Space: O(n)

time taken

• 14:20.50
  • recursion algorithms do not seem to come to me easily