C++でステッピングナンバー（Stepping Numbers）を効率的に求める方法

2つの整数 low と high が与えられたとき、範囲 [low, high] に含まれるすべての「ステッピングナンバー（Stepping Number）」を昇順に並べたリストを求めます。ステッピングナンバーとは、隣り合うどの桁同士も絶対差がちょうど1になる整数のことです。たとえば 321 はステッピングナンバーですが、421 は該当しません。入力が low = 0、high = 21 の場合、出力は [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21] となります。

解き方のアプローチ

この問題は、DFS（深さ優先探索）によって条件を満たす数を段階的に生成するのが効果的です。手順は以下のとおりです。

• 結果を一時的に保持する配列 temp を用意する
• solve() メソッドを作成する。引数は high、seed、len（len の初期値は0）
• seed が high を超えたら再帰を終了して戻る
• seed を temp 配列に追加する
• seed が 0 の場合：
  • 1〜9 の各 i に対して solve(high, i, 1) を呼び出す
• それ以外の場合：
  • lastDigit = seed mod 10 を計算する
  • lastDigit >= 1 かつ len + 1 <= 10 ならば、solve(high, (seed*10) + lastDigit − 1, len + 1) を呼び出す
  • lastDigit <= 8 かつ len + 1 <= 10 ならば、solve(high, (seed*10) + lastDigit + 1, len + 1) を呼び出す
• メイン処理では以下を実行する：
  • solve(high, 0, 0) を呼び出す
  • temp 配列をソートする
  • 答え用の配列 ans を作成する
  • i を 0 から temp のサイズ−1 までループし、temp[i] >= low ならば temp[i] を ans に追加する
  • ans を返す

なぜこの方法が有効なのか

範囲内のすべての整数を1つずつチェックすると非効率ですが、この手法では「次の桁は現在の末尾の桁±1である」という性質を利用し、ステッピングナンバーになり得る数だけを木構造的に生成できます。また、桁数を10桁までに制限しているのは、大きな数によるオーバーフローを防ぐためです。生成後にソートして下限値 low 以上の要素だけを取り出せば、目的のソート済みリストが得られます。

C++での実装例

以下のコードで実際の動作を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
    vector <lli> temp;
    void solve(int high,lli seed=0, int len =0){
        if(seed>high){
            return;
        }
        temp.push_back(seed);
        if(!seed){
            for(int i =1;i<=9;i++){
                solve(high,i,1);
            }
        } else {
            int lastDigit = seed%10;
            if(lastDigit>=1 && len+1<=10)
                solve(high, (seed*10) + lastDigit-1,len+1);
            if(lastDigit<=8 && len+1<=10)
                solve(high, (seed*10) + lastDigit+1,len+1);
        }
    }
    vector<int> countSteppingNumbers(int low, int high) {
        solve(high);
        sort(temp.begin(),temp.end());
        vector <int> ans;
        for(int i =0;i<temp.size();i++){
            if(temp[i]>=low)ans.push_back(temp[i]);
        }
        return ans;
    }
};
main(){
    Solution ob;
    print_vector(ob.countSteppingNumbers(0,40));
}

入力

0
40

出力

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34]