?LeetCode刷題實戰(zhàn)87： 擾亂字符串
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?擾亂字符串，我們先來看題面：
https://leetcode-cn.com/problems/scramble-string/
We can scramble a string s to get a string t using the following algorithm:
If the length of the string is 1, stop.
If the length of the string is > 1, do the following:
Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
Apply step 1 recursively on each of the two substrings x and y.
Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.
題意
示例?1:
輸入: s1 = "great", s2 = "rgeat"
輸出: true
示例?2:
輸入: s1 = "abcde", s2 = "caebd"
輸出: false
解題
題解
class?Solution:
????def?isScramble(self, s1: str, s2: str)?-> bool:
????????from?collections import?Counter
????????
????????def?determine(s1, s2):
????????????# 如果s1和s2構(gòu)成的字符不同，那么直接排除
????????????c1 = Counter(list(s1))
????????????c2 = Counter(list(s2))
????????????return?c1 == c2
????????
????????def?dfs(s1, s2):
????????????# 如果要判斷的s1和s2相等，返回True
????????????if?s1 == s2:
????????????????return?True
????????????if?not?determine(s1, s2):
????????????????return?False
????????????n = len(s1)
????????????# 枚舉拆分的位置將字符串拆分成兩個部分
????????????for?i in?range(1, n):
????????????????if?dfs(s1[:i], s2[:i]) and?dfs(s1[i:], s2[i:]) or?dfs(s1[:i], s2[n-i:]) and?dfs(s1[i:], s2[:n-i]):
????????????????????return?True
????????????return?False
????????
????????????
????????if?len(s1) != len(s2):
????????????return?False
????????if?len(s1) == 0:
????????????return?True
????????return?dfs(s1, s2)
總結(jié)
上期推文：