leetcode1585. 检查字符串是否可以通过排序子字符串得到另一个字符串【官方题解补充】

淡淡的烟草味﹌ 2022-11-05 03:10 7阅读 0赞

**思路**

s = "34521", 
    t = "23415"
    
    官方题解写的很清楚了，
    容易想到 s到t，首先解决把2从s的倒数第二个位置移到最前面
    这样就容易想到影响其他的数字
    可能导致其他的序列无法转换，这样与原问题就不等价了
    可以这样想
    将s中的2先和5排序
    然后2和4排序
    然后2和3排序
    这样就可以做到保证345的顺序的基础上 把2移到了最前面
    在不改变问题等价性的前提下，问题的规模就变小了1
    这样进行下去，知道最后一个元素即可
    
    用10和队列依次存储10个数在s中出现的位置
    这样可以快速获所需数dig在s中的最靠前位置
    然后就需要看比dig小的是不是排在s前面
    如果是 就无法转换
    
    如果不是
    算法继续进行至最后一个字符

class Solution { 
    public:
        bool isTransformable(string s, string t) { 
            vector<queue<int>> cnt(10);
            for(int i = 0;i< s.size();i++){ 
                int dig = s[i] - '0';
                cnt[dig].push(i);
            }
            
            for(int i=0;i<t.size();i++){ 
                int dig = t[i]-'0';
                if(cnt[dig].empty()){ 
                    return false;
                }
                else{ 
                    for(int j = 0;j < dig;j++){ 
                        if(!cnt[j].empty() && cnt[j].front() < cnt[dig].front() ){ 
                            return false;
                        }
                    }
                }
                cnt[dig].pop();
            }
            return true;
        }
    };

![在这里插入图片描述][20210303210608659.png]

[20210303210608659.png]: /images/20221023/2afb33b6957b4bfc84ddee0e8e4755ae.png