Valid Rolling String | tech::interview

Valid Rolling String | tech::interview

检查一个字符串是否包含k位a进制数的所有表示形式。
保证原字符串的所有字串都是合法的k位a进制数。"00110", a=2, k=2 => true （包括了00，01，10，11）

可以用rolling hash做，复杂度是O(N)。当然当字符串很大的话，naive的rolling hash肯定溢出了。
下面的代码假设1 <= a <= 10。

bool check_valid(const string& str, int a, int k) {

    int all_kinds = pow(a,k);

    if(str.size() - k + 1 < all_kinds) return false;



    uint64_t hash = 0, base = 1;

    for(int i = 0; i < k; ++i) {

        int num = str[i] - '0';

        if(num >= a) return false;

        hash += num * base;

        base *= 29;

    }

    base /= 29;

    

    unordered_set<uint64_t> record = { hash };

    for(int i = k; i < str.size(); ++i) {

        int num = str[i] - '0';

        if(num >= a) return false;

        hash = hash / 29 + num * base;

        record.insert(hash);

    }

    return record.size() == all_kinds;

}

TEST(check_valid("0011",2,2), false);

TEST(check_valid("001103",2,2), false);

TEST(check_valid("10110",2,2), false);

TEST(check_valid("00110",2,2), true);

TEST(check_valid("00111",2,2), false);

TEST(check_valid("4537860129",10,1), true);

TEST(check_valid("0123456789",10,2), false);

https://sites.google.com/site/codingbughunter/algorithm-question-discuss

Brute Force:

    public static boolean containNum(String str, int a, int k){
        HashSet<String> table = generateSet(a,k);

        for(int i=0; i<str.length()-k+1; i++){
            if(table.contains(str.substring(i,i+k))){
                System.out.println(str.substring(i,i+k));
                table.remove(str.substring(i,i+k));
            }
        }

        if(table.isEmpty()){
            return true;
        }
        return false;
    }

    private  static HashSet<String> generateSet(int a, int k){
        ArrayList<String> list = new ArrayList<String>();

        for(int i=0; i<k; i++){
            ArrayList<String> list2 = new ArrayList<String>();
            if( i == 0){
                for(int j=0 ;j < a; j++){

                    String tmp = ""+j;
                    list2.add(tmp);

                }
            }else{
                for(String tmp : list){
                    for(int j=0 ;j < a; j++){

                        String tmp2 = tmp+j;
                        list2.add(tmp2);

                    }
                }
            }
            list = list2;
        }

        HashSet<String> table = new HashSet<String>();
        for(String tmp : list){
            table.add(tmp);
        }
        return table;
    }

Read full article from Valid Rolling String | tech::interview