C++ Solution, 9ms, time O(n) space O(n), using String


  • 0
    class Solution {
    public:
        int magicalString(int n) {
            if (n == 0) return 0;
            if (n <= 3) return 1;
            string s = "122";
            int index = 2;
            char digit = '1';
            int tmp = s[index] - '0';
            int sum = 1;
            for (int i = 3; i < n; i++) {
                
                s += digit;
                sum += (digit == '1');
                tmp--;
                if (tmp == 0){
                    tmp = s[++index] - '0';
                    digit = changeDigit(s[i]);
                }
            }
            return sum;
        }
        char changeDigit(char digit) {
            if (digit == '1') return '2';
            return '1';
        }
    };
    
    

Log in to reply
 

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