leetcode 87 Scramble String(c++,beat 80%~100%)

el/2024/2/25 23:14:31

题解

符号:

  • S_(i-j):表示字符串s下标从i到j的字串。

思路
其实没什么规律,就是暴力枚举交换轴,然后每次有交换与不交换两种情况,递归判断是否可行。唯一剪枝就是假如S1_(i,j)=S2_(k,l),则他们所包含的字母的集合是相同的,如果不同,则不用再继续递归下去。
代码

class Solution {
public:int *sum1,*sum2;bool dfs(int l1,int r1,int l2,int r2,string &s1,string &s2){if(sum1[r1+1]-sum1[l1]!=sum2[r2+1]-sum2[l2]) return false;if(l1==r1){return s1[l1]==s2[l2];}int res =0;for(int i=0;i<r1-l1+1-1;i++){res|=dfs(l1,l1+i,l2,l2+i,s1,s2)&&dfs(l1+i+1,r1,l2+i+1,r2,s1,s2);if(res) break;res|=dfs(l1,l1+i,r2-i,r2,s1,s2)&&dfs(l1+i+1,r1,l2,r2-i-1,s1,s2);if(res) break;}return res;}bool isScramble(string s1, string s2) {if(s1.size()==0) return true;sum1= new int[s1.size()+1];sum2 = new int[s2.size()+1];sum1[0]=sum2[0]=0; for(int i=0;i< s1.size();i++){sum1[i+1]=(sum1[i]+((s1[i]*s1[i])^123563));sum2[i+1]=(sum2[i]+((s2[i]*s2[i])^123563));}return dfs(0,s1.size()-1,0,s2.size()-1,s1,s2);return false;}
};

http://www.ngui.cc/el/4894913.html

相关文章

【leetcode 142】 Linked List Cycle II 链表找环

链表找环 https://leetcode.com/problems/linked-list-cycle-ii/ class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: bool"""p1 headp2 headwhile p1 is not None and p1.next is not None:p1p1.next.nex…

VirtualBox安装增强工具时:Unable to install guest additions: unknown filesystem type 'iso9660'

搬运一下答案&#xff08;原文地址https://askubuntu.com/questions/596998/unable-to-install-guest-additions-unknown-filesystem-type-iso9660?newreg2d19e8256398418aa9fefb792def28a8&#xff09;&#xff0c;原因如答主所说。

【pyqt5】拖拽绘制矩形框

博主想自己做一个图片标注工具&#xff0c;用于制作目标检测数据集&#xff0c;其中一个功能就是拖拽鼠标选中矩形区域&#xff0c;参考了几篇博客&#xff0c;自己实现了一下&#xff0c;效果如下&#xff1a; 下面是实现&#xff1a; import sys,math from PyQt5.QtGui imp…

【numpy】ndarray交换两行(两列)、重新排列

numpy进行行(列)交换非常简便&#xff0c;因为numpy的下标访问是基于视图机制的&#xff0c;对子视图重新赋值即可。 a np.arange(12).reshape(3, 4) print(a) a[[0, 2]] a[[2, 0]] a运行结果: [[ 0 1 2 3][ 4 5 6 7][ 8 9 10 11]] array([[ 8, 9, 10, 11],[ 4, 5…

【python】python的for-else语法解释

若for循环正常结束&#xff0c;则执行else&#xff0c; 若for循环break&#xff0c;则不执行else。 for item in container:if search_something(item):# Found it!process(item)break else:# Didnt find anything..not_found_in_container()

【python】编码互转(16进制|bytes|base64|字符串)

基于python3 # 16进制转bytes byte_arr bytes.fromhex("1f2f3f4f") # bytes转16进制 byte_arr.hex() # bytes转base64&#xff0c;输入输出都是bytes import base64 base64.b64encode(byte_arr) # base64转bytes base64.b64decode(base64_byte_arr) # 字符串转byte…

【spark】spark dataframe空值·部分原因

数据类型不一致导致的空值 今天在写一个spark job(pyspark)时又遇到了&#xff0c;又遇到了数据处理的两大拦路虎之一的空数据问题&#xff0c;检查数据源&#xff0c;确定不会有空值后&#xff0c;开始检查代码。最终发现是代码之前的维护者使用了一个字符串作为一个long typ…

【git】强制使用远程分支(git pull -f ?)

git reset --hard origin/your-branch参考 https://stackoverflow.com/questions/1125968/how-do-i-force-git-pull-to-overwrite-local-files