題目意思就是說判斷s1能否經過題目所說的演算法得到s2，
題目中的演算法處理的位置為隨機，所以復現演算法基本無法得到s2
那么只能搜索了，
分析：
初始時：如果s1==s2，直接回傳true，
- 對于一個字串s1，在隨機位置分割s1，那么我們只能遍歷s1，假設當前位置為分割處，然后進行后續操作，來判斷是否能得到s2，分割是同時對s1和s2都進行分割，對兩者子串進行比較，
- 選取一個分割處后，假設分割后s1的兩字串為
s1_left,s1_right，s2的為s2_left,s2_right，題目中演算法的處理僅為‘交換’,所以要想判斷s1是不是能經過變換得到s2，只需要如下等式
//注意，這是偽代碼，實際上引數應該是根據起點和個數來切割得到的字串，
//因為切割得到的左右兩字串的size并不一定相等
isScramble(s1_left,s2_left)&&isScramble(s1_right,s2_right)//隨機決定，不交換
|| isScramble(s1_left,s2_right)&&isScramble(s1_right,s2_left)//隨機決定，交換
//兩者滿足其一即可，回傳true
如果第一層遞回遍歷所有切割點，都沒有找到，那么回傳false
初始代碼
class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1 == s2) return true;
int n = s1.size();
for (int i = 1; i < n; ++i)
{
string temp_s1_front, temp_s1_back, temp_s2_front, temp_s2_back,temp_s2_front_re,temp_s2_back_re;
temp_s1_front.assign(s1.begin(), s1.begin() + i);
temp_s1_back.assign(s1.begin() + i, s1.end());
temp_s2_front.assign(s2.begin(), s2.begin() + i);
temp_s2_back.assign(s2.begin() + i, s2.end());
temp_s2_front_re.assign(s2.end() - i, s2.end());
temp_s2_back_re.assign(s2.begin(), s2.end() - i);
if ( (isScramble(temp_s1_front, temp_s2_front)&&isScramble(temp_s1_back, temp_s2_back)) || (isScramble(temp_s1_front,temp_s2_front_re)&&isScramble(temp_s1_back,temp_s2_back_re)) )
{
return true;
}
}
return false;
}
};
邏輯沒問題，答案也沒錯，但是嚴重超時，
剪枝！
s1想僅通過交換得到s2，那么s1和s2里面的字母必定是同一個集合，并且，每個字母的個數也必定是相同的，
那么就很容易想到如下代碼：
unordered_map<char, int> s1Map;
unordered_map<char, int> s2Map;
for (char c : s1)
{
++s1Map[c];
}
for (char c : s2)
{
++s2Map[c];
}
if (s1Map.size() != s2Map.size()) return false;
for (auto x : s1Map)
{
if (s2Map[x.first] != x.second)
return false;
}
但是！別人直接sort，然后對比就完事，
菜鳥落淚
剪枝完畢，再來跑下試試
那么最后一招，記憶化遞回
在每次計算出某時的isScramble(s1,s2)時，塞到容器里，下次如果還遇到這倆s1,s2時，直接從容器里取，
OK，通過，
class Solution {
map<pair<string, string>, bool> checkmap;
public:
bool isScramble(string s1, string s2) {
if (checkmap.count(pair<string,string>(s1,s2)) > 0) return checkmap[pair<string,string>(s1,s2)];
if (s1 == s2)
{
checkmap[pair<string, string>(s1, s2)] = true;
return true;
}
string _s1 = s1, _s2 = s2;
sort(_s1.begin(), _s1.end());
sort(_s2.begin(), _s2.end());
if (_s1!=_s2)
{
checkmap[pair<string, string>(s1, s2)] = false;
return false;
}
int n = s1.size();
for (int i = 1; i < n; ++i)
{
//這里用的assign
/*string temp_s1_front, temp_s1_back, temp_s2_front, temp_s2_back, temp_s2_front_re, temp_s2_back_re;
temp_s1_front.assign(s1.begin(), s1.begin() + i);
temp_s1_back.assign(s1.begin() + i, s1.end());
temp_s2_front.assign(s2.begin(), s2.begin() + i);
temp_s2_back.assign(s2.begin() + i, s2.end());
temp_s2_front_re.assign(s2.end() - i, s2.end());
temp_s2_back_re.assign(s2.begin(), s2.end() - i);
if ((isScramble(temp_s1_front, temp_s2_front) && isScramble(temp_s1_back, temp_s2_back)) || (isScramble(temp_s1_front, temp_s2_front_re) && isScramble(temp_s1_back, temp_s2_back_re)))
{
checkmap[pair<string, string>(s1, s2)] = true;
return true;
}*/
//這里選擇用substr
//拋開服務器波動，substr占優勢（不過上面用的是迭代器，這里用的下標，應該不會有太大影響）
if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i, n - i), s2.substr(i, n - i)) ||
isScramble(s1.substr(0, i), s2.substr(n - i, i)) && isScramble(s1.substr(i, n - i), s2.substr(0, n - i)))
{
checkmap[pair<string, string>(s1, s2)] = true;
return true;
}
}
checkmap[pair<string, string>(s1, s2)] = false;
return false;
}
};
另外，容器這里我原本用的unordered_map，底層是hash表，但是發現unordered_map不能以pair作為Key，之前也遇到過了，這次又遇到，就查了一下，發現是因為unordered_map沒有寫以pair作為key的hash函式，
//我來嘗試寫一個
struct pairhash
{
template<typename T1,typename T2>
size_t operater()(const pair<T1,T2>& _p)
{
//第一個括號是生成物件，第二個帶參的括號是呼叫hash<T1>::operater()
auto _first = hash<T1>()(_p.first);
auto _second = hash<T2>()(_p.second);
return _first^_second;
}
}
//經測驗，OK
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/276942.html
標籤：其他
下一篇：序列計數