java - 不同子串的串联

Question

问题 - 按字典顺序排列给定字符串的所有不同子字符串并将它们连接起来。打印连接字符串的第 K 个字符。确保给定的 K 值有效，即存在第 K 个字符

输入格式 第一行将包含一个数字 T，即测试用例的数量。 每个测试用例的第一行将包含一个包含字符 (a−z) 的字符串，第二行将包含一个数字 K。

输出格式 打印第 K 个字符(字符串索引为 1)

限制 1≤T≤5 1≤长度≤105 K将是一个合适的整数。

示例输入#00

1
dbac
3

示例输出#00

c

说明#00

子串按字典顺序排列如下

a、ac、b、ba、bac、c、d、db、dba、dbac 将它们连接起来，我们得到

aacbbabaccddbdbadbac 该字符串中的第三个字符是 c，因此是答案。

这是我的代码:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution 
{

public static void gen(String str,int k)
{


      int i,c;ArrayList<String>al=new ArrayList<String>();
     for(c=0;c<str.length();c++)
    {
        for(i=1;i<=str.length()-c;i++)
        {
            String sub = str.substring(c,c+i);
            al.add(sub);
        }
    }

    HashSet hs = new HashSet();
    hs.addAll(al);
    al.clear();
    al.addAll(hs);

    String[] res = al.toArray(new String[al.size()]); 
    Arrays.sort(res);

    StringBuilder sb= new StringBuilder();

        for(String temp:res)
        {
           sb.append(temp);   
        }

    String s = sb.toString();
    System.out.println(s.charAt(k-1));
}


public static void main(String[] args) 
{
    Scanner sc = new Scanner (System.in);
    int t = Integer.parseInt(sc.nextLine());

        while((t--)>0)
        {
            String str = sc.nextLine();
            int k = Integer.parseInt(sc.nextLine());                 
            gen(str,k);

        }

   }
 }

这段代码对于小输入(如上面的测试用例)效果很好，但对于大输入，它要么超时，要么显示类似的内容，我确实明白问题出在内存上，任何替代方法都可以解决这个问题，或者无论如何重用相同的方法内存？？

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOfRange(Arrays.java:2694)
at java.lang.String.<init>(String.java:203)
at java.lang.String.substring(String.java:1913)
at Solution.gen(Solution.java:19)
at Solution.main(Solution.java:54)

Answer 1

根据给定的限制(最多 105 个字符)，您不应该遇到内存不足问题。也许您正在使用非常大的字符串进行测试。

所以，如果你有的话，这里有一些你浪费内存的地方:

• 填写完集合后，将其复制到列表中。这意味着子字符串集合的两个副本，而您将不再使用该集合。
• 将列表复制到数组后，您现在拥有子字符串集合的三个副本，尽管您不会再使用该列表。
• 现在您创建一个 StringBuilder 并将所有子字符串放入其中。但了解整个连接字符串并不是很有趣。我们只需要其中一个字符，那么为什么要把串联放在内存中呢？此外，在上面所有浪费的副本中，至少您没有复制子字符串本身。但现在您将它们附加到 StringBuilder 中，您正在创建它们的副本。这将是一个很长的字符串。
• 然后使用 toString() 将 StringBuilder 的内容复制到新字符串。这将创建一个非常大的连接字符串的副本(我们已经说过我们实际上并不需要)。

您已经得到了使用 TreeSet 并直接填充它的合理建议，而不是创建列表、集合和排序列表。下一步是从该集合中提取正确的字符而不实际保留连接的字符串。

因此，假设您的集合名为 set:

Iterator<String> iter = set.iterator();

int lengthSoFar = 0;
String str = null;

while ( lengthSoFar < k && iter.hasNext() ) {

     str = iter.next();           // Got the next substring;
     lengthSoFar += str.length();
}

// At this point we have the substring where we expect the k'th
// character to be.

System.out.println( str.charAt( k - lengthSoFar + str.length() - 1 );

请注意，程序获得较高的 k 值比获得较低的值需要更长的时间，但通常它会比构建整个连接字符串更快，因为一旦出现，您就会停止你得到了正确的子字符串。