69 lines
2.2 KiB
C++
69 lines
2.2 KiB
C++
// Source : https://leetcode.com/problems/largest-number-after-mutating-substring/
|
|
// Author : Hao Chen
|
|
// Date : 2021-11-12
|
|
|
|
/*****************************************************************************************************
|
|
*
|
|
* You are given a string num, which represents a large integer. You are also given a 0-indexed
|
|
* integer array change of length 10 that maps each digit 0-9 to another digit. More formally, digit d
|
|
* maps to digit change[d].
|
|
*
|
|
* You may choose to mutate a single substring of num. To mutate a substring, replace each digit
|
|
* num[i] with the digit it maps to in change (i.e. replace num[i] with change[num[i]]).
|
|
*
|
|
* Return a string representing the largest possible integer after mutating (or choosing not to) a
|
|
* single substring of num.
|
|
*
|
|
* A substring is a contiguous sequence of characters within the string.
|
|
*
|
|
* Example 1:
|
|
*
|
|
* Input: num = "132", change = [9,8,5,0,3,6,4,2,6,8]
|
|
* Output: "832"
|
|
* Explanation: Replace the substring "1":
|
|
* - 1 maps to change[1] = 8.
|
|
* Thus, "132" becomes "832".
|
|
* "832" is the largest number that can be created, so return it.
|
|
*
|
|
* Example 2:
|
|
*
|
|
* Input: num = "021", change = [9,4,3,5,7,2,1,9,0,6]
|
|
* Output: "934"
|
|
* Explanation: Replace the substring "021":
|
|
* - 0 maps to change[0] = 9.
|
|
* - 2 maps to change[2] = 3.
|
|
* - 1 maps to change[1] = 4.
|
|
* Thus, "021" becomes "934".
|
|
* "934" is the largest number that can be created, so return it.
|
|
*
|
|
* Example 3:
|
|
*
|
|
* Input: num = "5", change = [1,4,7,5,3,2,5,6,9,4]
|
|
* Output: "5"
|
|
* Explanation: "5" is already the largest number that can be created, so return it.
|
|
*
|
|
* Constraints:
|
|
*
|
|
* 1 <= num.length <= 10^5
|
|
* num consists of only digits 0-9.
|
|
* change.length == 10
|
|
* 0 <= change[d] <= 9
|
|
******************************************************************************************************/
|
|
|
|
class Solution {
|
|
public:
|
|
string maximumNumber(string num, vector<int>& change) {
|
|
bool replace = false;
|
|
for(int i=0; i<num.size(); i++) {
|
|
char n = num[i] - '0';
|
|
if (n < change[n] ) {
|
|
num[i] = change[n] + '0';
|
|
replace = true;
|
|
}else if (n > change[n] && replace ) {
|
|
break;
|
|
}
|
|
}
|
|
return num;
|
|
}
|
|
};
|