2

从这里得到这个问题。但是我能弄清楚的算法的运行时间真的很糟糕。这是问题：

如果 s 的所有字符都不同，则字符串 s 被称为唯一。字符串 s2 可以从字符串 s1 产生，如果我们可以删除 s1 的一些字符得到 s2。

如果 s1 的长度大于 s2 的长度，或者它们的长度相等并且 s1 在字典上大于 s2，则字符串 s1 比字符串 s2 更漂亮。

给定一个字符串 s，你必须找到可以从 s 产生的最漂亮的唯一字符串。

输入：输入的第一行是一个不超过 1,000,000(10^6) 个字符的字符串 s。s 的所有字符都是小写英文字母。

输出：打印可以从 s 产生的最漂亮的唯一字符串

样本输入：babab

样本输出：ba

我所做的是：

  1. 取出字符串并用单个字符删除所有相等的相邻字符。示例：输入：“bbbbbab” 输出：“bab”，这是这一步的输出。这成为下一步的输入。
  2. 现在为字符串中的每个唯一字符构建一个数组。该数组将在给定的输入数组中具有其出现的索引。
  3. 注意每个元素的第一次出现。查找出现次数的最小值和最大值。使用这个迭代所有可能的字符串，这些字符串可以由以索引 max 结尾的单词组成。取词典上最大的。
  4. 通过移动 max 重复上述操作。

我想要一个正确有效的算法，当输入字符串真的很大时可以扩展。

4

2 回答 2

4

如果效率太低，这里有一组实现，请分叉 repo 并使它们更有效率。

于 2013-07-18T13:43:32.777 回答
1

这是查找美丽子字符串的程序。它是完全优化的代码，使用动态编程具有较低的复杂性。

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-02T08:12:38.523 回答