小明思考

          Just a software engineer
          posts - 124, comments - 36, trackbacks - 0, articles - 0
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          日歷

          <2013年5月>
          2829301234
          567891011
          12131415161718
          19202122232425
          2627282930311
          2345678

          相冊

          My blogs

          搜索

          •  

          最新評論

          交叉字符串

          Posted on 2013-05-10 20:47 小明 閱讀(3239) 評論(4)  編輯  收藏 所屬分類: 數據結構和算法
          問題給定字符串s1,s2,s3,判斷s3是否可以由s1和s2交叉組成得到。

          例如:

          s1 = "aabcc",
          s2 = "dbbca",

          When s3 = "aadbbcbcac", return true.
          When s3 = "aadbbbaccc", return false.


          解法一:(遞歸)

          一個簡單的想法,是遍歷s3的每個字符,這個字符必須等于s1和s2的某個字符。如果都不相等,則返回false
          我們使用3個變量i,j,k分別記錄當前s1,s2,s3的字符位置。
          如果s3[k] = s1[i], i向后移動一位。如果s3[k]=s2[j],j向后移動一位。
          這個題目主要難在如果s1和s2的字符出現重復的時候,就有兩種情況,i,j都可以向后一位。
          下面的算法在這種情況使用了遞歸,很簡單的做法。但是效率非常差,是指數復雜度的。

          public class Solution {
              public boolean isInterleave(String s1, String s2, String s3) {
                  int l1 = s1.length();
                  int l2 = s2.length();
                  int l3 = s3.length();
                  
                  if(l1+l2!=l3){
                      return false;
                  }
                  
                  char[] c1 = s1.toCharArray();
                  char[] c2 = s2.toCharArray();
                  char[] c3 = s3.toCharArray();
                  
                  int i=0,j=0;
                  for(int k=0;k<l3;++k){
                      char c = c3[k];
                      boolean m1 = i<l1 && c==c1[i];
                      boolean m2 = j<l2 && c==c2[j];
                      if(!m1 && !m2){
                          return false;
                      }
                      else if(m1 && m2){
                          String news3 =  s3.substring(k+1);
                          return isInterleave(s1.substring(i+1),s2.substring(j),news3)
                                          || isInterleave(s1.substring(i),s2.substring(j+1),news3);
                      }
                      else if(m1){
                          ++i;
                      }
                      else{
                          ++j;
                      }
                  }
                  
                  return true;        
              }
          }


          解法二:(動態規劃)
          為了減少重復計算,就要使用動態規劃來記錄中間結果。

          這里我使用了一個二維數組result[i][j]來表示s1的前i個字符和s2的前j個字符是否能和s3的前i+j個字符匹配。

          狀態轉移方程如下:
          result[i,j] = (result[i-1,j] && s1[i] = s3[i+j])  || (result[i,j-1] && s2[j] = s3[i+j]);
          其中0≤i≤len(s1) ,0≤j≤len(s2)

          這樣算法復雜度就會下降到O(l1*l2)
          public class Solution {
             
          public boolean isInterleave(String s1, String s2, String s3) {
                  int l1 = s1.length();
                  int l2 = s2.length();
                  int l3 = s3.length();
                 
                  if(l1+l2!=l3){
                      return false;
                  }
                  
                  char[] c1 = s1.toCharArray();
                  char[] c2 = s2.toCharArray();
                  char[] c3 = s3.toCharArray();
                  
                  boolean[][] result = new boolean[l1+1][l2+1];
                  result[0][0] = true;
                  
                  for(int i=0;i<l1;++i){
                      if(c1[i]==c3[i]){
                          result[i+1][0] = true;
                      }
                      else{
                          break;
                      }
                  }
                  
                  for(int j=0;j<l2;++j){
                      if(c2[j]==c3[j]){
                          result[0][j+1] = true;
                      }
                      else{
                          break;
                      }
                  }
                  
                  
                  for(int i=1;i<=l1;++i){
                      char ci = c1[i-1];
                      for(int j=1;j<=l2;++j){
                          char cj = c2[j-1];
                          char ck = c3[i+j-1];
                             result[i][j] = (result[i][j-1] && cj==ck) || (result[i-1][j] && ci==ck);
                      }
                  }
                  
                  return result[l1][l2];
             }
          }

          評論

          # re: 交叉字符串  回復  更多評論   

          2013-05-11 10:19 by 開發吧
          今天正在搞這個問題,謝謝啦!

          # re: 交叉字符串  回復  更多評論   

          2013-05-12 21:09 by tb
          算法 對我有點啟發 謝謝

          # re: 交叉字符串  回復  更多評論   

          2013-05-13 11:23 by javanewer
          boolean[][] result = new boolean[l1+1][l2+1];
          這一句什么作用?

          # re: 交叉字符串[未登錄]  回復  更多評論   

          2013-05-15 18:57 by wang
          交叉字符串是用來干嘛的
          主站蜘蛛池模板: 宁都县| 台北县| 恭城| 孝昌县| 静安区| 枞阳县| 当雄县| 盐边县| 正蓝旗| 新化县| 贵德县| 西乌珠穆沁旗| 白山市| 惠安县| 黄山市| 巫溪县| 云南省| 龙门县| 楚雄市| 刚察县| 永昌县| 香格里拉县| 白玉县| 蕲春县| 大丰市| 五大连池市| 临西县| 马公市| 灵山县| 深州市| 吐鲁番市| 巴塘县| 商丘市| 元江| 衡南县| 株洲县| 图片| 安福县| 丹棱县| 澜沧| 孟连|