C++ recursive solution minimal hardcoding


  • -3
    D
    class Solution{
    public:
    	Solution () : IntVal {1,5,10,50,100,500,1000} , roman {'I', 'V' , 'X', 'L' ,'C', 'D' ,'M'} {}
    	std::string intToRoman(int num);
    private:
    	int IntVal[7];
    	char roman[7];
    	int fslt(int num);
    	std::string output;
    	void helper(int num);
    	void postProcess();
    	void str_replace( std::string &s, const std::string &search, const std::string &replace);
    };
    
    int Solution::fslt(int num){
    	if (num>=50){
    		if (num<100) return 3;
    		else if (num>=100 && num < 500) return 4;
    		else if (num>=500 && num < 1000) return 5;
    		else return 6;
    	}
    	else{ // num < 50
    		if (num>=10) return 2;
    		else if (num>=5) return 1;
    		else return 0;
    	}
    }
    
    void Solution::helper (int num){
    	int div = fslt(num);
    
    	
    	if (div == 0){
    		for (int i = 0; i <num ;i++){
    			output += roman[div];
    		}
    		 return;
    	}
    	else {
    		int rn = fslt(num);
    		int numTimes = num/IntVal[rn];
    		for (int i=0;i < numTimes; i++){
    			output += roman[rn];
    		}
    		helper(num-numTimes*IntVal[rn]);
    	}
    }
    
    void Solution::postProcess(){
    	str_replace(output, "DCCCC", "CM");
    	str_replace(output, "CCCC", "CD");
    	str_replace(output, "LXXXX", "XC");
    	str_replace(output, "XXXX", "XL");
    
    	str_replace(output, "VIIII", "IX");
    	str_replace(output, "IIII", "IV");
    }
    
    std::string Solution::intToRoman(int num){
    	Solution::helper(num);
    	Solution::postProcess();
    	return output;
    }
    
    void Solution::str_replace( std::string &s, const std::string &search, const std::string &replace)
    {
         for( size_t pos = 0; ; pos += replace.length() ) 
     	{
             pos = s.find( search, pos );
             if( pos == std::string::npos ) break;
     
             s.erase( pos, search.length() );
             s.insert( pos, replace );
         }
    }

  • 0
    B

    wow, I suppose this solution was a little too long


Log in to reply
 

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