5469. K 차 동작 변환 문자열

5469. K 차 동작 변환 문자열
제목 설명:
두 문자열 st 을 드 리 겠 습 니 다. k 번 작업 이내 에 문자열 st 으로 바 꾸 는 것 이 목표 입 니 다.
i 차 조작 시 (1 <= i <= k), 다음 과 같은 조작 을 선택 할 수 있 습 니 다.
문자열 s 에서 1 <= j <= s.length 을 만족 시 키 고 이전에 선택 되 지 않 았 던 임의의 하 표 j (하 표 는 1 부터) 를 선택 하고 이 위치의 문 자 를 i 번 으로 전환 합 니 다.아무런 조작 도 하지 않 습 니 다.1 차 문 자 를 바 꾸 는 것 은 알파벳 에 있 는 이 자모의 다음 자모 로 바 꾸 는 것 을 의미한다.
임의의 아래 표 시 는 'z' 번 으로 최대 'a' 번 만 조작 할 수 있다 는 것 을 기억 하 세 요.j 회 를 넘 지 않 는 작업 에서 문자열 1k 으로 바 꿀 수 있다 면 s 으로 돌아 가 십시오. 그렇지 않 으 면 t 으로 돌아 가 십시오.
예시 1:
  :s = "input", t = "ouput", k = 9true6'i'    6     'o'7'n'    7     'u'

예시 2:
  :s = "abc", t = "bcd", k = 10false1       t 。       1       'a'     'b'2                 t      。

예시 3:
  :s = "aab", t = "bbb", k = 27true1'a'    1     'b'27'a'    27     'b'

알림:true false 1 <= s.length, t.length <= 10^50 <= k <= 10^9 은 소문 자 를 포함 하고 있다.
문제 풀이 방향:
1) 、 s 사이 의 차 이 를 찾 아 t 보다 작 으 면;0 이상 이면 무시 합 니 다.2) 、 매번 계산 할 때마다 tmp = t[i] - s[i] + 260 +26 이 나타 나 면 kvST[tmp] 의 범위 내 에서 달성 할 수 없 으 며 ((kvST[tmp] - 1) * 26 + tmp) > k 에서 k 의 전환 을 실현 할 수 있다.
알림: 사실은 st 으로 바 꿀 수 있 습 니 다. map 의 숫자 는 vector 사이 이기 때문에 bs(t[i] - s[i])0 - 25 으로 대체 할 수 있 습 니 다.vector kvST(26,0)map kvST 을 하 표 로 저장 합 니 다. map kvST, key 은 하 표 가 일치 하 는 횟수 를 저장 합 니 다.bs(t[i] - s[i])value 중의 vector kvST(26,0) 을 직접 생략 하고 아래 표 시 된 map 에 대응 하여 아래 표 시 된 key 의 횟수 는 kvST[i] = value 임 을 나타 낸다.
코드 구현:
class Solution {
public:
    bool canConvertString(string s, string t, int k) {
        if (s.size() != t.size())
            return false ;
        map<int , int> kvST ;
        int i, tmp;
        for (i = 0 ; i < s.size() ; i ++)
        {
            // +26      `t[i] - s[i]`
            tmp = int(t[i] - s[i]) + 26 ;
            tmp = tmp >= 26 ? tmp - 26 : tmp ;
            if (tmp == 0)
                continue ;
            if (kvST.find(tmp) != kvST.end())
                kvST[tmp] ++ ;
            else
                kvST[tmp] = 1 ;
            if (((kvST[tmp] - 1) * 26 + tmp) > k)
                return false ;
        }
        return true ;
    }
};

복잡 도 계산:
시간 복잡 도: bs(t[i] - s[i]) 최대 문자열 을 옮 겨 다 녀 야 합 니 다.공간 복잡 도: value;최대 상수 개 – 26 개;

좋은 웹페이지 즐겨찾기