美麗的字符串

從here得到這個問題。但是我能算出的算法的運行時間非常糟糕。這裏是問題：美麗的字符串

如果s的所有字符都不相同，那麼字符串s被稱爲唯一。如果我們可以刪除s1的一些字符以獲得s2，則可以從字符串s1產生字符串s2。

如果s1的長度比s2的長度更長，則s1比s2更漂亮比s2的長度更長或長度相等，s1是按字典順序大於s2。

鑑於一個字符串s，你必須找到最美麗的獨特的字符串可以從s生產。

輸入：第一行輸入字符串不超過 1,000,000（10^6）個字符。 s的所有字符都是小寫字母英文字母。

輸出：打印最美麗獨特的字符串，它是從小號

樣品輸入producable：BABAB

樣本輸出：BA

我所做的是：

取出字符串，並刪除所有相同的相鄰字符與單個。例如：輸入：「bbbbbab」輸出：「bab」，這是此步驟的輸出。這成爲下一步的輸入。
現在爲字符串中的每個唯一字符構建一個數組。該數組將在給定的輸入數組中具有其出現的索引。
注意每個元素的第一次出現。查找出現的最小值和最大值。使用迭代遍歷所有可能的字符串，這些字符串可以由以索引max結尾的單詞形成。採取詞典學上最大的。
通過移動max來重複上述操作。

我想要一個正確和高效的算法，它可以在輸入字符串非常大時進行縮放。

來源

2013-07-18 kdurga

這裏是一組implementations如果這些效率太低，則分叉回購並使其更有效。

來源

2013-07-18 13:43:32 Woot4Moo

感謝您的鏈接...似乎是有效的。 – kdurga

不幸的是，在鏈接中提到的解決方案是錯誤的，我試圖實現它自己..嘗試輸入「abcdefabdc」輸出應該是「bcefad」，鏈接中給出的算法返回「bcdefa」.. – kdurga

答案似乎是「efadbc」，解決方案在這個鏈接似乎是正確的[鏈接]（http://skilldrill.wordpress.com/2013/06/28/beautiful-unique-strings/） – kdurga

這裏是找到Beautiful substring的程序。它是完全優化的代碼，使用動態編程的複雜性較低。

static String LCSubStr(String X,String Y, int m, int n)// Longest Common substring 
{ 
     int LCSarr[][]=new int[m+1][n+1]; 
     int max = 0; 
     int max_index=0; 
     for (int i=0; i<=m; i++) 
     { 
      for (int j=0; j<=n; j++) 
      { 
       if (i == 0 || j == 0) 
       LCSarr[i][j] = 0; 

       else if (X.charAt(i-1) == Y.charAt(j-1))//if char matches 
       { 
        LCSarr[i][j] = LCSarr[i-1][j-1] + 1; 
        if(max < LCSarr[i][j]) 
        { 
          max=LCSarr[i][j]; 
          max_index=i; //Index points at which last char matched 
         } 
       } 
       else LCSarr[i][j] = 0; 
      } 
     } 
     return (X.substring(max_index-max,max_index)); 

    } 

    public static void main(String[] args) 
    { 
      Scanner sc=new Scanner(System.in); 

      System.out.print("Enter String 1: "); 
      String str=new String(sc.nextLine()); 
      str=str.toLowerCase(); 
      String temp2="";//string with no duplicates 
      HashMap<Integer,Character> tc = new HashMap<Integer,Character>();//create a hashmap to store the char's 
      char [] charArray = str.toCharArray(); 
      for (Character c : charArray)//for each char 
      { 
        if (!tc.containsValue(c))//if the char is not already in the hashmap 
        { 
         temp2=temp2+c.toString();//add the char to the output string 
         tc.put(c.hashCode(),c);//and add the char to the hashmap 
        } 
       } 
       System.out.print("\nBeatiful substring of given String is: "); 
       System.out.println(LCSubStr(str,temp2,str.length(),temp2.length()));//Find Longest common substring which gives us actually beautiful string 
     }

來源

2014-09-02 08:12:38

@GeraldSchneider：謝謝你給我一個建議。我試圖根據你的建議改進我上面給出的答案，你很樂意提供進一步的建議。 –

美麗的字符串

回答

相關問題