leetcode 87. 擾亂字符串(dp)

使用下面描述的算法可以擾亂字符串 s 得到字符串 t :
如果字符串的長度為 1 ,算法停止
如果字符串的長度 > 1 ,執行下述步驟:
在一個隨機下標處將字符串分割成兩個非空的子字符串。即,如果已知字符串 s ,則可以將其分成兩個子字符串 x 和 y ,且滿足 s = x + y 。
隨機 決定是要「交換兩個子字符串」還是要「保持這兩個子字符串的順序不變」。即,在執行這一步驟之后,s 可能是 s = x + y 或者 s = y + x 。
在 x 和 y 這兩個子字符串上繼續從步驟 1 開始遞歸執行此算法。
給你兩個 長度相等 的字符串 s1 和 s2,判斷 s2 是否是 s1 的擾亂字符串。如果是,返回 true ;否則,返回 false 。

示例 1:

輸入:s1 = “great”, s2 = “rgeat”
輸出:true
解釋:s1 上可能發生的一種情形是:
“great” --> “gr/eat” // 在一個隨機下標處分割得到兩個子字符串
“gr/eat” --> “gr/eat” // 隨機決定:「保持這兩個子字符串的順序不變」
“gr/eat” --> “g/r / e/at” // 在子字符串上遞歸執行此算法。兩個子字符串分別在隨機下標處進行一輪分割
“g/r / e/at” --> “r/g / e/at” // 隨機決定:第一組「交換兩個子字符串」,第二組「保持這兩個子字符串的順序不變」
“r/g / e/at” --> “r/g / e/ a/t” // 繼續遞歸執行此算法,將 “at” 分割得到 “a/t”
“r/g / e/ a/t” --> “r/g / e/ a/t” // 隨機決定:「保持這兩個子字符串的順序不變」
算法終止,結果字符串和 s2 相同,都是 “rgeat”
這是一種能夠擾亂 s1 得到 s2 的情形,可以認為 s2 是 s1 的擾亂字符串,返回 true
示例 2:

輸入:s1 = “abcde”, s2 = “caebd”
輸出:false
示例 3:

輸入:s1 = “a”, s2 = “a”
輸出:true

解題思路

dp[i1][i2][len] 代表 s1[i1,i1+len),s2[i2,i2+len)是否互為擾亂字符串,0代表未判斷,1和-1分別代表是和否。
狀態轉移:兩種情況
i為長度,范圍是(1到 len-1)

  • 1.沒有交換順序的,直接將s1,s2切割為前一段為i長度,后一端為len-i長度,分別比較s1,s2的兩個子串,如果兩個子串也是擾亂字符串,當前字符串就滿足擾亂字符串的定義。
  • 2.交換順序后,將s1切割為前一段為i長度,后一端為len-i長度,而將s1切割為前一段為len-i長度,后一端為i長度,將s1的前端和s2的后端作比較,s1的后端和s2前端作比較

代碼

public class Solution {int [][][] dp;String ss1,ss2;public boolean isScramble(String s1, String s2) {int n=s1.length();ss1=s1;ss2=s2;dp=new int[n][n][n+1];return dfs(0,0,n);}public boolean  dfs(int i1,int i2,int len){if(dp[i1][i2][len]!=0){return dp[i1][i2][len]==1;}if(ss1.substring(i1,i1+len).equals(ss2.substring(i2,i2+len))){dp[i1][i2][len]=1;return true;}if(!check(i1,i2,len)){dp[i1][i2][len]=-1;return false;}for(int i=1;i<len;i++){if(dfs(i1, i2, i)&&dfs(i1+i, i2+i, len-i)){dp[i1][i2][len]=1;return true;}if(dfs(i1, i2+len-i, i)&&dfs(i1+i, i2, len-i)){dp[i1][i2][len]=1;return true;}}dp[i1][i2][len]=-1;return false;}public boolean check(int i1,int i2,int len){int[] check=new int[26];for (int i=i1;i<i1+len;i++)check[ss1.charAt(i)-'a']++;for(int i=i2;i<i2+len;i++)check[ss2.charAt(i)-'a']--;for(int i=0;i<26;i++)if(check[i]!=0) return false;return true;}}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/391406.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/391406.shtml
英文地址,請注明出處:http://en.pswp.cn/news/391406.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

頁面布局

頁面布局兩大類&#xff1a;   主站&#xff1a; 1 <div classpg-header> 2 <div stylewidth:980px;margin:0 auto;> 3 內容自動居中 4 </div> 5 <div classpg-content></div> 6 <div classpg-footer></div&…

sonar:默認的掃描規則

https://blog.csdn.net/liumiaocn/article/details/83550309 https://note.youdao.com/ynoteshare1/index.html?id3c1e6a08a21ada4dfe0123281637e299&typenote https://blog.csdn.net/liumiaocn/article/details/83550309 文本版&#xff1a; soanr規則java版 …

多變量線性相關分析_如何測量多個變量之間的“非線性相關性”?

多變量線性相關分析現實世界中的數據科學 (Data Science in the Real World) This article aims to present two ways of calculating non linear correlation between any number of discrete variables. The objective for a data analysis project is twofold : on the one …

wp博客寫文章500錯誤_500多個博客文章教我如何撰寫出色的文章

wp博客寫文章500錯誤Ive written a lot of blog posts. Somewhere north of 500 to be exact. All of them are technical. 我寫了很多博客文章。 確切地說是在500以北的某個地方。 所有這些都是技術性的。 About two dozen of them are actually good. 實際上大約有兩打是不錯…

leetcode 220. 存在重復元素 III(排序)

給你一個整數數組 nums 和兩個整數 k 和 t 。請你判斷是否存在 兩個不同下標 i 和 j&#xff0c;使得 abs(nums[i] - nums[j]) < t &#xff0c;同時又滿足 abs(i - j) < k 。 如果存在則返回 true&#xff0c;不存在返回 false。 示例 1&#xff1a; 輸入&#xff1a…

ON DUPLICATE KEY UPDATE

INSERT INTO ON DUPLICATE KEY UPDATE 與 REPLACE INTO&#xff0c;兩個命令可以處理重復鍵值問題&#xff0c;在實際上它之間有什么區別呢&#xff1f;前提條件是這個表必須有一個唯一索引或主鍵。1、REPLACE發現重復的先刪除再插入&#xff0c;如果記錄有多個字段&#xff0c…

os.path 模塊

os.path.abspath(path) #返回絕對路徑os.path.basename(path) #返回文件名os.path.commonprefix(list) #返回list(多個路徑)中&#xff0c;所有path共有的最長的路徑。os.path.dirname(path) #返回文件路徑os.path.exists(path) #路徑存在則返回True,路徑損壞返回Falseos.path…

探索性數據分析(EDA):Python

什么是探索性數據分析(EDA)&#xff1f; (What is Exploratory Data Analysis(EDA)?) If we want to explain EDA in simple terms, it means trying to understand the given data much better, so that we can make some sense out of it.如果我們想用簡單的術語來解釋EDA&a…

微服務框架---搭建 go-micro環境

1.安裝micro 需要使用GO1.11以上版本 #linux 下 export GO111MODULEon export GOPROXYhttps://goproxy.io # windows下設置如下環境變量 setx GO111MODULE on setx GOPROXY https://goproxy.io # 使用如下指令安裝 go get -u -v github.com/micro/micro go get -u -v github.co…

angular dom_Angular 8 DOM查詢:ViewChild和ViewChildren示例

angular domThe ViewChild and ViewChildren decorators in Angular provide a way to access and manipulate DOM elements, directives and components. In this tutorial, well see an Angular 8 example of how to use the two decorators.Angular中的ViewChild和ViewChild…

浪潮之巔——IT產業的三大定律

http://www.cnblogs.com/ysocean/p/7641540.html轉載于:https://www.cnblogs.com/czlovezmt/p/8325772.html

DStream算子講解(一)

先把目錄列好&#xff0c;方便有條理的進行整理轉載于:https://www.cnblogs.com/leodaxin/p/7507600.html

aws 靜態網站_如何使用AWS托管靜態網站-入門指南

aws 靜態網站When I created my first portfolio last year, I based it on what I had learned from freeCodeCamp (HTML, CSS and a little JavaScript). 去年創建我的第一個投資組合時 &#xff0c;我基于從freeCodeCamp (HTML&#xff0c;CSS和一些JavaScript)中學到的知識…

leetcode 27. 移除元素(雙指針)

給你一個數組 nums 和一個值 val&#xff0c;你需要 原地 移除所有數值等于 val 的元素&#xff0c;并返回移除后數組的新長度。 不要使用額外的數組空間&#xff0c;你必須僅使用 O(1) 額外空間并 原地 修改輸入數組。 元素的順序可以改變。你不需要考慮數組中超出新長度后面…

使用TVP批量插入數據

TVP&#xff08;全稱 :Table-Valued Parameter&#xff09; 叫做表值參數(Table-Valued Parameter)是SQL2008的一個新特性。顧名思義&#xff0c;表值參數表示你可以把一個表類型作為參數傳遞到函數或存儲過程里。 第一步&#xff1a;創建一個Type類型和寫入數據的原始表結構相…

python:找出兩個列表中相同和不同的元素(使用推導式)

#接口返回值 list1 [張三, 李四, 王五, 老二] #數據庫返回值 list2 [張三, 李四, 老二, 王七]a [x for x in list1 if x in list2] #兩個列表表都存在 b [y for y in (list1 list2) if y not in a] #兩個列表中的不同元素print(a的值為:,a) print(b的值為:,b)c [x for x …

springcloud(六):配置中心git示例

隨著線上項目變的日益龐大&#xff0c;每個項目都散落著各種配置文件&#xff0c;如果采用分布式的開發模式&#xff0c;需要的配置文件隨著服務增加而不斷增多。某一個基礎服務信息變更&#xff0c;都會引起一系列的更新和重啟&#xff0c;運維苦不堪言也容易出錯。配置中心便…

寫作工具_4種加快數據科學寫作速度的工具

寫作工具I’ve been writing about data science on Medium for just over two years. Writing, in particular, technical writing can be time-consuming. Not only do you need to come up with an idea, write well, edit your articles for accuracy and flow, and proofr…

leetcode 91. 解碼方法(dp)

解題思路 記憶化搜索&#xff0c;記錄已經計算過的子問題 代碼 func numDecodings(s string) int {temp:make([]int,len(s),len(s))for i : range temp {temp[i]-1}return de(s,0,temp) } func de(s string,cur int,dp []int) int {if curlen(s){return 1}if dp[cur]!-1{re…

python數據結構與算法

2019獨角獸企業重金招聘Python工程師標準>>> http://python.jobbole.com/tag/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/ 轉載于:https://my.oschina.net/u/3572879/blog/1611369