C++ dp solution very easy to understand


  • 0
    Q
    class Solution {
    public:
        int maximumSwap(int num) {
            if(num<10)
                return num;
            string s;
            s = to_string(num);
            vector<int> v(s.size(),0);
            v[s.size()-1] = s[s.size()-1] - '0';
            for(int i=s.size()-2;i>=0;i--){
                v[i] = max(v[i+1],s[i] - '0');
            }
            
            for(int i=0;i<s.size();i++){
                if(s[i]-'0' != v[i]){
                    for(int j=s.size()-1;j>i;j--){
                        if(s[j]-'0' == v[i]){
                            char c = s[j];
                            s[j] = s[i];
                            s[i] = c;
                            return stoi(s);
                        }
                    }
                }    
            }
            return num;
        }
    };
    

Log in to reply
 

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