# LeetCode 1585 Check If String Is Transformable With Substring Sort Operations

```class Solution {
public:
int c[100005];
int a[100005];
vector<int> pos[10];
int n;
bool isTransformable(string s, string t) {

for(int i = s.length()-1;i>=0;i--)
{
int num = s[i]-'0';
pos[num].push_back(i+1);
}

n = s.length();
for(int i=0;i<=n;i++)
{
c[i] = INT_MAX;
}

for(int i=0;i<s.length();i++)
{
a[i+1]=s[i]-'0';
}

for(int i=0;i<t.length();i++)
{
if(pos[t[i]-'0'].size()==0)
return false;
int p = pos[t[i]-'0'].back();
pos[t[i]-'0'].pop_back();
int m = get(1,p);
if(m!=t[i]-'0')
return false;

}

return true;

}

int lowbit(int x)
{
return x&(-x);
}

{
a[index] = num;
while(index<=n)
{
int l = index-lowbit(index)+1;
int m = get(l, index-1);
if(l==index)
{
c[index]=a[index];
}
else if(min(m, a[index])!=c[index])
{
c[index]=min(m, a[index]);
}
else
{
break;
}
index+=lowbit(index);
}
}

int get(int l, int r)
{
if(l>r)
return INT_MAX;
int ans = INT_MAX;
while(r>=l)
{
if(r-lowbit(r) < l-1)
{
ans = min(ans, a[r]);
r--;
}
else
{
ans = min(ans, c[r]);
r-=lowbit(r);
}
}
return ans;
}
};```

0 条评论

• ### [002] 一文了解Python中的常用字符串操作

Asthe co-founder of Microsoft says, I invite you to continue stretching your min...

• ### lua Standard Libraries

The standard Lua libraries provide useful functions that are implemented directl...

• ### 2018-11-21

This section comprises a glossary of all the keywords — grouped by category and ...

• ### java开发_org.apache.commons.lang.StringUtils工具类源码

http://www.cnblogs.com/hongten/archive/2012/11/08/java_null.html

• ### LeetCode Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating chara...

• ### Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

• ### LeetCode Weekly Contest 28解题思路

好吧，不要被这道题的例子给骗了。要求输出的最大，意思就是求除第一个元素之外的其他division最小，而不断连除就是第二部分的最小值，所以有如下代码：

• ### Python基础篇 strings 03

找出子字符串出现频次和出现的索引位置核查是否存在字符串并找出其索引位置查找所有字符的出现次数和索引

• ### No.003 Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters Total Accepted: 167158 Total Subm...

• ### C++版- Leetcode 3. Longest Substring Without Repeating Characters解题报告

Leetcode 3. Longest Substring Without Repeating Characters

• ### 【Leet Code】3. Longest Substring Without Repeating Characters

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### Leetcode solution 1036: Escape a Large Maze

New leetcode solution video on YouTube.com/baozitraining

• ### LeetCode3.滑动窗口: 双指针法(Kotlin语言)-无重复字符的最长子串

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

• ### 【玩转腾讯云】python help函数

python 3.x版本虽然比2.x少了一些内置函数，但是 python 内置 函数没有60个，也有40个，那么多内置函数你记得过来吗？为了方便使用，pytho...

• ### 写给开发者的机器学习指南（八）

Ranking emails based on their content(Recommendation system)

• ### [LeetCode]HashTable主题系列{第3题}

1. 内容介绍 开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程，具体内容层次按照{题目，分析，初解，初解结果，优化解...

• ### Leetcode3——Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating chara...

• ### Leetcode 算法 －3. Longest Substring Without Repeating Characters

我们以ababcbb为例说明, 这里hash表的值-1是初始值, 这样在方便做+1操作. index 作为开始索引值, 起初index为0， 这是理所当然的。当...