Question

java题, 要求:输入一个数m,找出str中m个字符的所有子字符串

例如，输入："abc" m=2 ，则输出："ab" "ac" "bc"
输入："abcd" m=3 ， 则输出："abc" "acd" "bcd" "abd"

这个题想了好久还是做不出来 ，我想先求字符串中所有可能的组合，然后筛选出长度为m的字符串，可是做不出来，请大家帮忙看看啊？？

Answer 1

简单一点的思路是用递归：

public class Class1 {
  
  //求组合数 C(m,n)
  public static int C(int m,int n){
    int c=1;
    int k=1;
    for (int i=1;i<=m;i++){
      c=c*(n+1-i);
      k=k*i;
      }
    return (c/k);
    }
  
  //获取str中所有长度为m的子串
  //递归方法
  public static String[] getSubString(String str,int m){
    String[] s;//保存子串
    int count=0;//子串计数器
    int n=str.length();//原字符串长度
    if (m>n || m<=0){
      s=new String[]{};
      return s;//如果子串长度大于字符串长度，或子串长度小于等于0，则不会有满足要求的子串
    }
    else{
      s=new String[C(m,n)];//保存子串，子串个数为C(m,n)
    }
    if (m==1){//若子串长度为1，则返回字符串的每个字符即可
      int i;
      for (i=0;i<str.length();i++){
        count++;
        s[count-1]=""+str.charAt(i);
      }
    }
    else{//否则，长度为m的子串由长度为m-1的子串再加一个字符组成
      for (int j=m-1;j<str.length();j++){
        String[] ss=getSubString(str.substring(0, j),m-1);
        for (int k=0;k<ss.length;k++){
          count++;
          s[count-1]=ss[k]+str.charAt(j);
        }
      }
    }
    return s;
  }
  
   public static void main(String args[]) { 
     String str="abcd";
     int m=2;
     String[] ss=getSubString(str,m);
     for(String s : ss)
       System.out.println(s);
   }
}

如果不用递归，可以用下列算法：

求“abc”，m=2的子串，等价于求 "123"，m=2的子串。可以看出，符合条件的子串是12,23,13。也就是从123 三个数字里，找出所有长度为2的升序排列。

 

如果字符串长度为n，那么等价的命题就是从1到n n个数字里，找出所有长度为m的升序排列。

 

此时的解法为：

步骤1：可以找出所有的长度为m的排列。这可以通过一个长度为m的栈来实现；

步骤2：筛选出其中符合升序的排列（每一位数字大于前一位）。这样也自然会过滤掉有重复数字的排列。

 

最后，将这些升序排列映射回子字符串即可。

 

下面的代码在此思路上稍微做了改进：

package project1;
public class Class1 {
  
  //求组合数 C(m,n)
  public static int C(int m,int n){
    int c=1;
    int k=1;
    for (int i=1;i<=m;i++){
      c=c*(n+1-i);
      k=k*i;
      }
    return (c/k);
    }
  
  //获取str中所有长度为m的子串
  public static String[] getSubString(String str,int m){
    String[] s=new String[]{};//保存子串
    int count=0;//子串数目
    int n=str.length();//原字符串长度
    if (m>n || m<=0)
      return s;//如果子串长度大于字符串长度，则不会有满足要求的子串
    else
      s=new String[C(m,n)];//保存子串
    int[] k=new int[m];
    for (int i=0;i<m;i++){
      k[i]=i;
      }
    int p=m-1;
    int end=0;
    while (end==0){
      //保存当前得到的子串
      count++;
      String temps="";
      for (int i=0;i<m;i++)
        temps+=str.charAt(k[i]);
      s[count-1]=temps;
      
      //获取下一个子串
      k[p]=k[p]+1;
      while (p>=0 && k[p]-p>n-m){
        p=p-1;
        if (p>=0)
          k[p]=k[p]+1;
      }
      if (p>=0){
        for (int i=p+1;i<m;i++)
          k[i]=k[p]+i-p;
        p=m-1;
      }else{
        end=1;
      }
    }
    return s;
  }
  
   public static void main(String args[]) { 
     String str="abcd";
     int m=2;
     String[] ss=getSubString(str,m);
     for(String s : ss)
       System.out.println(s);
   }
}

结果：

ab
ac
ad
bc
bd
cd
Process exited with exit code 0.

 

以上两种算法均未考虑原字符串中有重复字符的情况。如果有重复字符，需要在得到的子串中过滤掉重复子串。代码这里就不写了。

Answer 2

这个问题如果字符串长度不是很长的话,可以考虑用回溯来处理

String str = "abc";
int m = 2;
StringBuffer sb= new StringBuffer();
boolean[] useable = new boolean[str.length()];
public viod subStr(int n){
if(n == 0){
System.out.println(sb.toString());
return ;
}
for(int i=0; i<str.length();i++){
if(useable[i]){
sb.append(str.charAt(i));
useable[i]=false;
subStr(n-1);
useable[i]=true;
sb.delete(sb.length()-1,sb.length());
}
}
}