s*******f
发帖数: 1114 | 1 1. get index of s1 in s2, for each char in s1, mark position is s2.
here "tiger" in "itreg" is [1, 0, 4, 3, 2]
stops和posts is: 2 3 1 0 4
//For duplication, always pick nearer one first. I use "set" to deal with
duplication in code.
At first I use brute force here with O(n square). But when using
hash_map >, it goes to O(n), or queue hm[256]
.no need to use "set" for duplication.
2. rule for eat: you can eat neighbour if your high or low bound
can "touch" neighbour.
here [1, 0, 4, 3, 2] -> 1 eat 0 [0, 1], 4 eat 3 [3, 4], then eat 2 [2, 4],
than eat [0, 1] --> [0, 4]
3. if you can eat into 1 snake, return true;
//This is bottom up solution. Look the following tree itself for ideas.
//since no standard proof provided, welcome to use your test case to beat
this:)
//zzzz码遍本版，回报本版zzzz
//scramble string
//7. scramble string，对一个string，比如tiger，可以随便找一个partition tree
// tiger
// / \
// ti ger
/// \ / \
//t i g er
// / \
// e r
//你可以选择在每个非叶子节点翻转或者不翻转两个儿子的顺序，比如可以变成
// itreg
// / \
// it reg
/// \ / \
//t i g re
// / \
// e r
//那么就称itreg是可以通过tiger串scramble得到的
//给s1, s2，求是否能找到s1一颗partition tree和翻转方案，使得得到s2
//other than 3D dynamic P. I got some new idea
//
bool DoIntArray(int a[], int len){
if (len < 4)
return true;
stack > sk;
for (int i = 0; i < len; ++i){
pair pa = make_pair(a[i], a[i]);
while (!sk.empty()){
if (pa.first - sk.top().second == 1){ //eat left
side
pa.first = sk.top().first;
sk.pop();
} else if (sk.top().first - pa.second == 1){
pa.second = sk.top().second;
sk.pop();
} else {
break;
}
}
sk.push(pa);
}
if (sk.size() == 1)
return true;
else
return false;
}
bool Scramble(const string &s1, const string &s2){
if (s1.size() != s2.size())
return false;
int *index = new int[s1.size()];
int k = 0;
queue mp[256];
for (int j = 0; j < s2.size(); ++j){
mp[s2[j]].push(j);
}
for (int i = 0; i < s1.size(); ++i){
if (mp[s1[i]].empty())
return false;
index[k++] = mp[s1[i]].front();
mp[s1[i]].pop();
}
/* set visited;
for (int i = 0; i < s1.size(); ++i){
int j = 0;
for (; j < s2.size(); ++j){
if (visited.find(j) != visited.end())
continue;
if (s1[i] == s2[j]){
visited.insert(j);
break;
}
}
if (j == s2.size()) return false;
}
*/ bool b = DoIntArray(index, s1.size());
delete[] index;
return b;
}
void TestScramble(){
bool a = Scramble("tiger", "itreg");
bool b = Scramble("abcd", "bdac");
bool c = Scramble("tigerr", "itrerg");
bool d = Scramble("tigerr", "irertg");
} | c****p
发帖数: 6474 | 2 stops和posts中的两个s怎么标号？
【在 s*******f 的大作中提到】
: 1. get index of s1 in s2, for each char in s1, mark position is s2.
: here "tiger" in "itreg" is [1, 0, 4, 3, 2]
: stops和posts is: 2 3 1 0 4
: //For duplication, always pick nearer one first. I use "set" to deal with
: duplication in code.
: At first I use brute force here with O(n square). But when using
: hash_map >, it goes to O(n), or queue hm[256]
: .no need to use "set" for duplication.
: 2. rule for eat: you can eat neighbour if your high or low bound
: can "touch" neighbour.
| s*******f
发帖数: 1114 | 3 nice point.
stops和posts is: 2 3 1 0 4
For duplication, always pick nearer one first. I use "set" to deal with
duplication.
【在 c****p 的大作中提到】
: stops和posts中的两个s怎么标号？
| j********e
发帖数: 1192 | 4 我的想法是先找root分割位置。满足下面条件的就行：
1）该位置把原s1和s2分成了4个字串，这4个字串包含的字符集应该两两相同。
【在 s*******f 的大作中提到】
: 1. get index of s1 in s2, for each char in s1, mark position is s2.
: here "tiger" in "itreg" is [1, 0, 4, 3, 2]
: stops和posts is: 2 3 1 0 4
: //For duplication, always pick nearer one first. I use "set" to deal with
: duplication in code.
: At first I use brute force here with O(n square). But when using
: hash_map >, it goes to O(n), or queue hm[256]
: .no need to use "set" for duplication.
: 2. rule for eat: you can eat neighbour if your high or low bound
: can "touch" neighbour.
| w****x
发帖数: 2483 | 5 贴一个递归和DP的:
/*
scramble string，judge if one string can be scrambled to another one
tiger
/ \
ti ger
/ \ / \
t i g er
/ \
e r
rotation is allowded
itreg
/ \
it reg
/ \ / \
t i g re
/ \
e r
then tiger can be changed to itreg
*/
bool _inner_can_scramble(const char* szStr1, const char* szStr2, int n);
bool CanScramble(const char* szStr1, const char* szStr2)
{
assert(szStr1 && szStr2);
int nLen1 = strlen(szStr1);
int nLen2 = strlen(szStr2);
if (nLen1 != nLen2)
return false;
return _inner_can_scramble(szStr1, szStr2, nLen1);
}
bool _inner_can_scramble(const char szStr1[], const char szStr2[], int n)
{
assert(szStr1 && szStr2);
if (0 >= n || (n == 1 && szStr1[0] == szStr2[0]))
return true;
for (int i = 1; i < n; i++)
{
if ( _inner_can_scramble(szStr1, szStr2, i) &&
_inner_can_scramble(szStr1+i, szStr2+i, n-i))
return true;
if (_inner_can_scramble(szStr1, szStr2+n-i, i) &&
_inner_can_scramble(szStr1+i, szStr2, n-i))
return true;
}
return false;
}
//Obviously, previous recursion solution contains duplicated
//calculation, use DP to save the duplicated results
bool CanScrambleDP(const char* szStr1, const char* szStr2)
{
int nLen1 = strlen(szStr1);
int nLen2 = strlen(szStr2);
if (nLen1 != nLen2)
return false;
//allocate
//pRec[i][j][k] means can szStr1(i ... i+k)
//be scrambled to szStr2(j ... j+k)
bool*** pRec = new bool**[nLen1];
for (int i = 0; i < nLen1; i++)
{
pRec[i] = new bool*[nLen1];
for (int j = 0; j < nLen1; j++)
{
pRec[i][j] = new bool[nLen1];
for (int k = 0; k < nLen1; k++)
pRec[i][j][k] = false;
}
}
for (int i = 0; i < nLen1; i++)
{
for (int j = 0; j < nLen1; j++)
pRec[i][j][0] = (szStr1[i] == szStr2[j]);
}
for (int l = 1; l < nLen1; l++)
{
for (int i = 0; i+l < nLen1; i++)
{
for (int j = 0; j+l < nLen1; j++)
{
bool bRes = false;
for (int k = i+1; k <= i+l; k++)
{
if ((pRec[i][j][k-i-1] && pRec[k][k][i+l-k])
|| (pRec[i][j+l+1-k+i][k-i-1] && pRec[k][j][i+l-k]))
{
pRec[i][j][l] = true;
break;
}
}
}
}
}
bool bRet = pRec[0][0][nLen1-1];
for (int i = 0; i < nLen1; i++)
{
for (int j = 0; j < nLen1; j++)
delete []pRec[i][j];
delete []pRec[i];
}
delete []pRec;
return bRet;
} | b****e
发帖数: 45 | 6 字符集相同并不一定保证scramble可行，比如以下两个字符串：
"abcde"
"dbeac"
似乎没有办法通过scramble得到。
【在 j********e 的大作中提到】
: 我的想法是先找root分割位置。满足下面条件的就行：
: 1）该位置把原s1和s2分成了4个字串，这4个字串包含的字符集应该两两相同。
:
| S****h
发帖数: 115 | 7 赞lz的想法！！
不过我在leetcode上测试了下，small test, 下面连个测试案例没通过。不知道是我少
考虑什么地方么？感觉主要问题就是‘always pick nearer one first'，当然可以通
过permutation来fix.
"abab", "bbaa" false true
"bbaa", "abab" false true
【在 s*******f 的大作中提到】
: 1. get index of s1 in s2, for each char in s1, mark position is s2.
: here "tiger" in "itreg" is [1, 0, 4, 3, 2]
: stops和posts is: 2 3 1 0 4
: //For duplication, always pick nearer one first. I use "set" to deal with
: duplication in code.
: At first I use brute force here with O(n square). But when using
: hash_map >, it goes to O(n), or queue hm[256]
: .no need to use "set" for duplication.
: 2. rule for eat: you can eat neighbour if your high or low bound
: can "touch" neighbour.
| s*******f
发帖数: 1114 | 8 nice. Let me double check. ‘always pick nearer one first' just try to
avoid twisted, but need proof. so now maybe wrong.
watch muvie first
【在 S****h 的大作中提到】
: 赞lz的想法！！
: 不过我在leetcode上测试了下，small test, 下面连个测试案例没通过。不知道是我少
: 考虑什么地方么？感觉主要问题就是‘always pick nearer one first'，当然可以通
: 过permutation来fix.
: "abab", "bbaa" false true
:
: "bbaa", "abab" false true
:
| j********e
发帖数: 1192 | 9 我没有说字符集相同就能scramble，字符集相同是必要条件，而不充分。
我的做法是，先找到一个位置i在s1,j在s2使得分割后的4个字符串两两
有相同的字符集（i=j 或者i=N-j)。然后接着对这2对字符串继续做同样
的事情连寻找分割位置。这样递归下去，如果有某对字符串无法找到分割
位置，则表示失败。否则，最后分隔最小的字符串只有一个字符。就可以
判断scramble成功。
问题是，如果有多个分割位置，是否任选一个都可以？如果必须测试每个可能的分割位置，那复杂度就不好说了。
下面是我的简单实现代码，通过了leetcode的online judge (包括judge large)。这段代码中会处理所有可能的分割位置。如果只选第一个可能的分割位置，有一个测试失败了。
#include
#include
#include
#include
using namespace std;
#define BITMAP_LEN 256
bool compare_char_set(const char *s1, const char *s2, int len) {
int bitmap[BITMAP_LEN];
int i;
//char t1[len+1], t2[len+1];
//strncpy(t1, s1, len);
//strncpy(t2, s2, len);
//t1[len] = t2[len] = 0;
//printf("Compare t1: %s, t2: %s, n is %d\n", t1, t2, len);
memset(bitmap, 0, sizeof(int)*BITMAP_LEN);
for(i=0; i
bitmap[(unsigned int)s1[i]] ++;
bitmap[(unsigned int)s2[i]] --;
}
for(i=0; i
if(bitmap[i]!=0)
return false;
return true;
}
bool test_scramble(const char *s1, const char *s2, int n) {
if(!s1 || !s2)
return false;
if(n == 1)
if(*s1 == *s2)
return true;
else
return false;
//char t1[n+1], t2[n+1];
//strncpy(t1, s1, n);
//strncpy(t2, s2, n);
//t1[n] = t2[n] = 0;
//printf("Test t1: %s, t2: %s, n is %d\n", t1, t2, n);
// Find root place
for(int i=1; i
bool find_root = false;
if(compare_char_set(s1, s2, i) && compare_char_set(s1+i, s2+i, n-i)) {
find_root = true;
//printf("Find first type root position %d\n", i);
if(test_scramble(s1, s2, i) && test_scramble(s1+i, s2+i, n-i))
return true;
}
if(compare_char_set(s1, s2+(n-i), i) && compare_char_set(s1+i, s2, n-i)) {
find_root = true;
//printf("Find second type root position %d\n", i);
if(test_scramble(s1, s2+(n-i), i) && test_scramble(s1+i, s2, n-i))
return true;
}
//if(find_root)
// break;
}
return false;
}
class Solution {
public:
bool isScramble(string s1, string s2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s1.length() != s2.length())
return false;
return test_scramble(s1.c_str(), s2.c_str(), s1.length());
}
};
【在 b****e 的大作中提到】
: 字符集相同并不一定保证scramble可行，比如以下两个字符串：
: "abcde"
: "dbeac"
: 似乎没有办法通过scramble得到。
| B*******1
发帖数: 2454 | 10 My code
pass all the test on 1337 online judge.
bool isScrambleHelper(const string &s1, const string &s2, map
string>, bool> &myMap)
{
pair key = make_pair(s1, s2);
if (myMap.count(key) != 0) return myMap[key];
bool result = false;
if (s1 == s2) {
result = true;
} else if (s1.size() != s2.size() ) {
result = false;
} else {
for (int i = 1; i < s1.size(); i++) {
if ((isScrambleHelper(s1.substr(0, i), s2.substr(0,i),myMap) &&
isScrambleHelper(s1.substr(i, s1.size()-i), s2.substr(i, s2.
size()-i), myMap)) ||
(isScrambleHelper(s1.substr(0, i), s2.substr(s2.size()-i,i),
myMap) &&
isScrambleHelper(s1.substr(i, s1.size()-i), s2.substr(0,s1.
size()-i), myMap))) {
result = true;
break;
}
}
}
myMap[key] = result;
return result;
}
class Solution {
public:
bool isScramble(string s1, string s2) {
map, bool> myMap;
return isScrambleHelper(s1, s2, myMap);
}
}; | | | j********e
发帖数: 1192 | 11 你的代码太暴力，Judge Large需要2s左右，有时候还会超时。
我前面贴的代码大概需要20多ms。
,
【在 B*******1 的大作中提到】
: My code
: pass all the test on 1337 online judge.
: bool isScrambleHelper(const string &s1, const string &s2, map: string>, bool> &myMap)
: {
: pair key = make_pair(s1, s2);
: if (myMap.count(key) != 0) return myMap[key];
: bool result = false;
: if (s1 == s2) {
: result = true;
| t*****j
发帖数: 1105 | 12 我也回报一下。递归的，复杂度是二叉树层数*字符串个数。空间复杂度也是O(n).
今晚刚写的，test过了。
bool isSubAnargm(string parent, string child)
{
if(parent.empty() && child.empty()) return true;
for(unsigned int i = 0; i< child.size(); i++)
{
if (parent.find(child[i]) < 0) return false;
}
if (parent.find(child[0]) > parent.find(child[child.size()-1]))
{
reverse(parent.begin(), parent.end());
};
if (parent.compare(child) == 0) return true;
int currentMaxPosition = -1;
int validMaxLength = -1;
for(unsigned int i = 0; i< child.size()-1; i++)
{
if (currentMaxPosition < (signed int)(parent.find(child[i])))
{
currentMaxPosition = parent.find(child[i]);
}
if (currentMaxPosition == i)
{
validMaxLength = currentMaxPosition;
}
}
if(validMaxLength == -1)
{
return false;
};
return isSubAnargm(parent.substr(0,validMaxLength+1),
child.substr(0,
validMaxLength+1)) && isSubAnargm(parent.substr(validMaxLength+1,
parent.
size()-validMaxLength-1), child.substr(validMaxLength+1, parent.size()-
validMaxLength-1));
}
with
【在 s*******f 的大作中提到】
: 1. get index of s1 in s2, for each char in s1, mark position is s2.
: here "tiger" in "itreg" is [1, 0, 4, 3, 2]
: stops和posts is: 2 3 1 0 4
: //For duplication, always pick nearer one first. I use "set" to deal with
: duplication in code.
: At first I use brute force here with O(n square). But when using
: hash_map >, it goes to O(n), or queue hm[256]
: .no need to use "set" for duplication.
: 2. rule for eat: you can eat neighbour if your high or low bound
: can "touch" neighbour.
| c********p
发帖数: 1969 | | x*****0
发帖数: 452 | | m********c
发帖数: 105 | 15 贴一个我的recursive代码，time complexity是O(n^2)，large Judge用了144ms，不
是最优解，但是容易理解
bool isScramble(string s1, string s2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (s1 == s2)
return true;
int size = s1.size();
int value1=0, value2=0;
for (int i=0; i
value1 += (s1[i]-'a');
value2 += (s2[i]-'a');
}
if (value1 != value2)
return false;
for (int i=1; i
if (isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.
substr(i), s2.substr(i)))
return true;
if (isScramble(s1.substr(0,i), s2.substr(size-i)) && isScramble(
s1.substr(i), s2.substr(0,size-i)))
return true;
}
return false;
} | s*******n
发帖数: 305 | |
|
