文字列のすべてのサブシーケンス（部分列）を出力する3つの方法を解説

問題の概要

この問題では、1つの文字列が与えられ、その文字列のすべての部分列（サブシーケンス）を出力することが求められます。部分列とは、元の文字列から一部の文字を削除して作られる文字列のことであり、文字の並び順を入れ替えることはできません。

具体的な入出力例を見てみましょう。

入力：xyz
出力：x, y, z, xy, yz, xz, xyz

解説：上記の例では、文字を削除するだけで部分列を生成しており、並べ替えは一切行っていません。たとえば「xz」は「xyz」から「y」を取り除いたものですが、「zx」のような順序の入れ替えは許されません。

なお、長さnの文字列の部分列は（空文字列を含めれば）2ⁿ個存在します。この問題へのアプローチは複数あるため、ここでは代表的な3つの方法を紹介します。※コード例は考え方を示しやすいようJavaで記述していますが、同じロジックはC++など他の言語でも実装できます。

方法1：各文字を「選ぶ／選ばない」で再帰的に生成する

1つ目の方法は、文字列の各要素に対して「選択する」か「除外する」かを決めながら、再帰的に部分列を作っていく方法です。いくつかの文字を残し、残りを削除することで部分列を構築します。

コード例

import java.util.*;
class Main{
    public static ArrayList<String>subStringSeq=new ArrayList<String>();
    public static void main(String[] args) {
        String s="pqrs";
        System.out.println("All the substring found are :");
        findSubString(s,"");
        System.out.println(subStringSeq);
    }
    public static void findSubString(String s, String ans) {
        if(s.length()==0){
            subStringSeq.add(ans);
            return;
        }
        findSubString(s.substring(1),ans+s.charAt(0)) ;
        findSubString(s.substring(1),ans);
    }
}

実行結果

[pqrs, pqr, pqs, pq, prs, pr, ps, p, qrs, qr, qs, q, rs, r, s]

先頭の文字を採用するケースと採用しないケースの2つに分岐して再帰呼び出しを行うことで、すべての組み合わせが網羅されます。

方法2：文字列を走査しながら重複を排除して生成する

2つ目の方法は、文字列を二重ループで走査して部分文字列を取り出し、さらにそこから文字を1つずつ削除して部分列を派生させていく方法です。ここではHashSetを使って部分列を保存し、すでに見つかった部分列との重複チェックを行います。

コード例

import java.util.HashSet;
public class Main{
    static HashSet<String> subString = new HashSet<>();
    static void findSubString(String str){
        for (int i = 0; i < str.length(); i++) {
            for (int j = str.length(); j > i; j--) {
                String sub_str = str.substring(i, j);
                if (!subString.contains(sub_str))
                    subString.add(sub_str);
                for (int k = 1; k < sub_str.length() - 1; k++) {
                    StringBuffer sb = new StringBuffer(sub_str);
                    sb.deleteCharAt(k);
                    if (!subString.contains(sb));
                        findSubString(sb.toString());
                }
            }
        }
    }
    public static void main(String[] args){
        String s = "pqrs";
        System.out.println("The subsequence is ");
        findSubString(s);
        System.out.println(subString);
    }
}

実行結果

[rs, pq, qr, pr, qs, ps, prs, p, pqr, q, r, s, pqs, qrs, pqrs]

HashSetを利用しているため、同じ内容の部分列が自動的に除外され、重複のない結果が得られます。

方法3：文字を固定して再帰的に部分列を組み立てる

3つ目の方法は、文字列の各文字を順番に「固定」し、その固定した文字を起点として後ろへ部分列を伸ばしていく方法です。このメソッドを再帰的に呼び出すことで、すべての部分列が生成されます。

コード例

class Main {
    static void subString(String str, int n,
    int index, String curr){
        if (index == n){
            return;
        }
        System.out.print(curr + ", ");
        for (int i = index + 1; i < n; i++){
            curr += str.charAt(i);
            subString(str, n, i, curr);
            curr = curr.substring(0, curr.length() - 1);
        }
    }
    static void printSubStrings(String str){
        int index = -1;
        String curr = "";
        subString(str, str.length(), index, curr);
    }
    public static void main(String[] args){
        String str = "pqrs";
        System.out.println("The subStrings are :") ;
        printSubStrings(str);
    }
}

実行結果

p, pq, pqr, pqrs, pqs, pr, prs, ps, q, qr, qrs, qs, r, rs, s

開始位置を固定して文字を追加→再帰→末尾を削除、という流れを繰り返すことで、辞書順に近い形ですべての部分列が出力されます。

まとめ

文字列のすべての部分列を出力するには、再帰を活用するのが最も自然なアプローチです。方法1は各文字の採用・不採用を二分岐で決めるシンプルな手法、方法2は既存の部分文字列から文字を削除して派生させ、HashSetで重複を防ぐ手法、方法3は開始位置を固定して前方へ伸ばしていく手法です。それぞれ実装のしやすさや計算量が異なるため、文字列の長さや重複の扱いなどの要件に応じて使い分けることをおすすめします。