【学习笔录】每周一道算法题：串联字串

Author： YH_evIs
发布时间：November 25, 2019
29226views
7 comments
1052字数
Categories：算法

##题目##
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

**示例 1：**
```javascript
//输入：
let s = "barfoothefoobarman",
let words = ["foo","bar"]
//输出：
[0,9]
//解释：
//从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
//输出的顺序不重要, [9,0] 也是有效答案。
```

**示例 2：**
```javascript
//输入：
let s = "wordgoodgoodgoodbestword",
let words = ["word","good","best","word"]
//输出：
[]
```

----------
##解答##
```javascript
var findSubstring = function(s, words) {
let len;
if(words.length>0){
len=words[0].length;
}
return   existsStr(s,words,len);
};
function initListMap(list){
let map={};
for(let i of list){
if(!map[i]){
map[i]={start:0};
}
map[i].start+=1;
}
return map;
}
function formateListMap(map){
for(let i in map){
map[i]["exist"]=map[i].start;
}
}
function existsStr(str,list,len){
let rst=[];
if(len){
let long=len*list.length;
let listMap=initListMap(list);
for(let i=0;i+long<=str.length;i++){
let st=str.substr(i,long);
formateListMap(listMap);
let exist=true;
for(let k=0;k<long;k+=len){
let s=st.substr(k,len);
if(listMap[s]&&listMap[s].exist>0){
listMap[s].exist=listMap[s].exist-1;
}else {
exist=false;
break;
}
}
if(!exist){
continue;
}
rst.push(i);
}
}
return rst;
}
```

Last modification：December 9th, 2019 at 11:13 am

如果觉得我的文章对你有用，请随意赞赏

7 comments

两仪橙

November 29th, 2019 at 10:19 am

第二段代码在上面基础上，修改为了用栈进行运算，而不是递归，状态记录方式改为状态压缩，用二进制进行计算，理论上可以处理log2(sizeof(unsigned long long))长度的keys，懒得检测了

#include <vector>
#include <stack>
#include <set>
#include <iostream>
using namespace std;


struct Trie_node{
    int count;
    Trie_node *children[26];
};
struct stackNode{
    Trie_node *cur_node;
    int pos;
    unsigned long long state;
    string cur_str;
};
string target = "babaababcabcdcbbbcbcdbabaababcabcdcbbbcdbcbabaababcabcdbbcdcbbcbabaababcabcdbbcdbccbbabaababcabcdbcbbcdbcbabaababcabcdbcbbcbcdbabaababcabcdbbccbbcdbabaababcabcdbbcbcdcbaababcabcdbbcbcdcbbabaababcabcdbbcbcdbabcbaababcabcdbbccbbcdbabaababcabcdbbccbbabbcdabcbabcdabcbcdbabbbcaabcbabcdabcbcdbababbcabcbabcdabcbcdbababcbabcbabcdabcbcdbabbcababcbabcdabcbcdbabbcbaabcbabcdabcabcbcdbbababcbabcdabcabcbcdbabbbbcdabccbbabbcabcdaabbbcdabccbbabbcaabcdabbbcdabccbbabbcaababcdbbcdabccbbababbcabcdabbcdabccbbababbcaabcdbbcdabccbbabababcdbcabbcdabccbbabababcdabccbabcdababbcdabbbcabccbabcdababbcdababcbbccbabcdababbcdababcbcbcbabcdababbcdabbcabcbcbabcdababbcdabbcbabccbabcdabababcbcbcdbabcbabcdabababcbcbcdabbcbabcdabababcbcbbcdab";
vector<string> keys = {"a", "ab", "abc", "abcd", "b", "bc", "bcd", "cb", "bab"};
set<int> ans;
stack<stackNode> STACK;

Trie_node *root;
int len;

Trie_node *create_node(){
    Trie_node *newNode = new Trie_node();
    newNode->count = 0;
    for(int i = 0; i < 26; i++) newNode->children[i] = NULL;
    return newNode;
}


void insert_node(char *key){
    Trie_node *cur = root;
    char *tmp = key;
    while(*tmp){
        if(cur->children[*tmp-'a'] == NULL){
            cur->children[*tmp-'a'] = create_node();
        }
        cur = cur->children[*tmp-'a'];
        tmp++;
    }
    cur->count += 1;
}

bool isOK(unsigned long long state){
    for(int i = 0; i < keys.size(); i++){
        if(state & 1 == 1){
            state = state >> 1;
            continue;
        }
        else{
            return false;
        }
    }
    return true;
}

void visit(Trie_node *cur, int pos, unsigned long long state, string curstr){
    if(isOK(state)){
        ans.insert(pos-len);
        return;
    }
    if(pos >= target.length() || cur->children[target[pos]-'a'] == NULL || curstr.length() > len) return;
    stackNode newnode;
    if(cur->children[target[pos]-'a']->count != 0){
        for(int i = 0; i < keys.size(); i++){
            if(keys[i]==curstr+target[pos] && !(state&(1<<i))){
                newnode.cur_node = root;
                newnode.pos = pos+1;
                newnode.state = state | (1<<i);
                newnode.cur_str = "";
                STACK.push(newnode);
                break;
            }
        }
    }
    newnode.state = state;
    newnode.cur_node = cur->children[target[pos]-'a'];
    newnode.pos = pos + 1;
    newnode.cur_str = curstr+target[pos];
    STACK.push(newnode);
}

void DFS(){
    while(!STACK.empty()){
        stackNode top = STACK.top();
        STACK.pop();
        visit(top.cur_node, top.pos, top.state, top.cur_str);
    }
}

int main(int argc, char *argv[]){
    len = 0;
    root = create_node();
    for(auto it : keys){
        insert_node(&it[0]);
        len += it.length();
    }
    for(int i = 0; i <= target.length() - len; i++){
        stackNode start = {root, i, 0, ""};
        STACK.push(start);
        DFS();
    }
    for(auto it : ans) cout << it << " ";
    cout << endl;
    return 0;
}

下面是这次检测的字符集

input:
s = babaababcabcdcbbbcbcdbabaababcabcdcbbbcdbcbabaababcabcdbbcdcbbcbabaababcabcdbbcdbccbbabaababcabcdbcbbcdbcbabaababcabcdbcbbcbcdbabaababcabcdbbccbbcdbabaababcabcdbbcbcdcbaababcabcdbbcbcdcbbabaababcabcdbbcbcdbabcbaababcabcdbbccbbcdbabaababcabcdbbccbbabbcdabcbabcdabcbcdbabbbcaabcbabcdabcbcdbababbcabcbabcdabcbcdbababcbabcbabcdabcbcdbabbcababcbabcdabcbcdbabbcbaabcbabcdabcabcbcdbbababcbabcdabcabcbcdbabbbbcdabccbbabbcabcdaabbbcdabccbbabbcaabcdabbbcdabccbbabbcaababcdbbcdabccbbababbcabcdabbcdabccbbababbcaabcdbbcdabccbbabababcdbcabbcdabccbbabababcdabccbabcdababbcdabbbcabccbabcdababbcdababcbbccbabcdababbcdababcbcbcbabcdababbcdabbcabcbcbabcdababbcdabbcbabccbabcdabababcbcbcdbabcbabcdabababcbcbcdabbcbabcdabababcbcbbcdab
keys = {"a", "ab", "abc", "abcd", "b", "bc", "bcd", "cb", "bab"};
output:
0 3 4 6 9 13 15 16 18 21 24 25 27 30 34 40 42 45 46 48 51 55 56 59 63 66 67 69 72 76 77 82 84 87 88 90 93 97 98 100 105 108 109 111 114 118 119 123 126 129 130 132 135 139 140 142 147 168 169 171 174 178 179 181 184 189 190 192 195 199 20000 202 210 211 213 216 220 221 223 225 231 232 252 254 256 260 263 266 269 273 274 275 277 281 284 287 288 289 290 291 292 294 295 296 297 298 302 303 305 308 309 311 314 315 316 317 319 323 326 329 330 332 334 336 338 340 344 347 357 35369 361 365 366 368 369 371 374 375 377 378 399 400 403 406 408 411 413 418 420 421 424 427 429 432 434 435 441 442 445 448 450 453 458 462 463 466 469 471 472 473 474 475 476 478 483 484 487 490 492 495 497 500 504 505 508 511 513 514 515 5 516 517 518 522 525 543 546 548 552 553 556 559 561 565 567 569 573 574 577 580 582 585 586 588 590 594 595 598 601 603 608 609 611 615 616 619 622 624 626 630 632 636 637 640 651 653 657 658 659 660 661 664 666 669 671 672 674 678 679 5
682 685 687 693

YH_evIs
November 29th, 2019 at 10:40 am

@两仪橙
发不出来肯定是数据集的锅￣﹃￣

Reply

两仪橙

November 29th, 2019 at 10:18 am

优化了代码

这段代码在第一版代码基础上优化了对于重复字符集的判断和重复前缀的判断

#include <vector>
#include <iostream>
#include <set>
using namespace std;


struct Trie_node{
    int count;
    Trie_node *children[26];
};
string target = "babaababcabcdcbbbcbcdbabaababcabcdcbbbcdbcbabaababcabcdbbcdcbbcbabaababcabcdbbcdbccbbabaababcabcdbcbbcdbcbabaababcabcdbcbbcbcdbabaababcabcdbbccbbcdbabaababcabcdbbcbcdcbaababcabcdbbcbcdcbbabaababcabcdbbcbcdbabcbaababcabcdbbccbbcdbabaababcabcdbbccbbabbcdabcbabcdabcbcdbabbbcaabcbabcdabcbcdbababbcabcbabcdabcbcdbababcbabcbabcdabcbcdbabbcababcbabcdabcbcdbabbcbaabcbabcdabcabcbcdbbababcbabcdabcabcbcdbabbbbcdabccbbabbcabcdaabbbcdabccbbabbcaabcdabbbcdabccbbabbcaababcdbbcdabccbbababbcabcdabbcdabccbbababbcaabcdbbcdabccbbabababcdbcabbcdabccbbabababcdabccbabcdababbcdabbbcabccbabcdababbcdababcbbccbabcdababbcdababcbcbcbabcdababbcdabbcabcbcbabcdababbcdabbcbabccbabcdabababcbcbcdbabcbabcdabababcbcbcdabbcbabcdabababcbcbbcdab";
vector<string> keys = {"a", "ab", "abc", "abcd", "b", "bc", "bcd", "cb", "bab"};
set<int> ans;

Trie_node *root;
int len;

Trie_node *create_node(){
    Trie_node *newNode = new Trie_node();
    newNode->count = 0;
    for(int i = 0; i < 26; i++) newNode->children[i] = NULL;
    return newNode;
}

void insert_node(char *key){
    Trie_node *cur = root;
    char *tmp = key;
    while(*tmp){
        if(cur->children[*tmp-'a'] == NULL){
            cur->children[*tmp-'a'] = create_node();
        }
        cur = cur->children[*tmp-'a'];
        tmp++;
    }
    cur->count += 1;
}

bool isOK(int visit[]){
    for(int i = 0; i < keys.size(); i++){
        if(visit[i] == 0) return false;
    }
    return true;
}

void DFS(Trie_node *cur, int pos, int visit[], string curstr){
    if(isOK(visit)){
        ans.insert(pos-len);
        return;
    }
    if(pos >= target.length() || cur->children[target[pos]-'a'] == NULL || curstr.length() > len) return;
    DFS(cur->children[target[pos]-'a'], pos+1, visit, curstr+target[pos]);
    if(cur->children[target[pos]-'a']->count != 0){
        for(int i = 0; i < keys.size(); i++){
            if(keys[i]==curstr+target[pos] && visit[i]==0){
                visit[i] = 1;
                DFS(root, pos+1, visit, "");
                visit[i] = 0;
                return;
            }
        }
    }
}

int main(int argc, char *argv[]){
    len = 0;
    root = create_node();
    for(auto it : keys){
        insert_node(&it[0]);
        len += it.length();
    }
    int *visit = new int[keys.size()];
    for(int i = 0; i <= target.length() - len; i++){
        for(int j = 0; j < keys.size(); j++) visit[j] = 0;
        DFS(root, i, visit, "");
    }
    for(auto it : ans) cout << it << " ";
    cout << endl;
    return 0;

两仪橙

November 27th, 2019 at 05:17 pm

原数据集太小了，就换了个数据集
生成数据集的python代码也放这里

def permutations(arr, position, end):
    if position == end:
        for i in arr:
            f.write(str(i))
        f.write("\n")
    else:
        for index in range(position, end):
            arr[index], arr[position] = arr[position], arr[index]
            permutations(arr, position+1, end)
            arr[index], arr[position] = arr[position], arr[index]
 
with open("test.txt", "w") as f: 
    arr=["abc", "def", "ghi", "jkl", "mno", "pqr", "stu", "vwx", "yz"]
    permutations(arr, 0, len(arr))

数据集一共36万行，最后随机选取其中一部分，

input:
s = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuyzvwxabcdefghijklmnopqrvwxstuyzabcdefghijklmnopqrvwxyzstuabcdefghijklmnopqryzvwxstughidefjklstumnoabcyzpqrvwxghidefjklstumnovwxabcpqryzghidefjklstumnovwxabcyzpqrghidefjklstumnovwxpqrabcyzghidefjklstumnovwxpqryzabcghidefjklstumnovwxyzpqrabcghidefjklstumnovwxyzabcpqrghidefjklstumnoyzabcvwxpqrghidefjklstumnoyzabcpqrvwxghidefjklstumnoyzvwxabcpqrghidefjklstumnoyzvwxpqrabcghidefjklstumnoyzpqrvwxabcghidefjklstumnoyzpqrabcvwxjklstupqrvwxghimnoabcdefyzjklstupqrvwxghimnoabcyzdefjklstupqrvwxghimnoyzabcdefjklstupqrvwxghimnoyzdefabcjklstupqrvwxghidefmnoabcyzjklstupqrvwxghidefmnoyzabcjklstupqrvwxghidefabcmnoyzjklstupqrvwxghidefabcyzmnojklstupqrvwxghidefyzabcmnostuvwxmnopqrghiabcyzdefjklstuvwxmnopqrghiabcyzjkldefstuvwxmnopqrghidefabcjklyzstuvwxmnopqrghidefabcyzjklstuvwxmnopqrghidefjklabcyzstuvwxmnopqrghidefjklyzabcstuvwxmnopqrghidefyzjklabcstuvwxmnopqrghidefyzabcjklstuvwxmnopqrghiyzabcdefjklyzabcdefghijklvwxmnostupqryzabcdefghijklmnostuvwxpqryzabcdefghijklmnostupqrvwxyzabcdefghijklmnovwxstupqryzabcdefghijklmnovwxpqrstuyzabcdefghijklmnopqrvwxstuyzabcdefghijklmnopqrstuvwx";
words = {"abc", "def", "ghi", "jkl", "mno", "pqr", "stu", "vwx", "yz"};

output:
0 3 6 9 12 15 18 21 26 29 32 35 38 41 44 52 55 58 61 64 67 70 73 78 81 84 87 90 93 96 101 104 130 133 136 139 142 145 156 159 162 165 168 171 174 177 182 185 188 191 194 197 200 208 211 214 217 220 223 226 229 234 237 240 243 246 249 252 257 260 263 266 269 272 275 278 280 286 289 292 295 298 301 309 312 315 318 321 324 327 329 332 338 341 344 347 350 353 355 364 367 370 373 376 379 381 384 390 393 396 399 402 405 407 413 416 419 422 425 428 431 433 436 442 468 471 474 477 480 483 486 489 494 497 500 503 506 509 512 517 520 523 526 529 532 535 538 540 546 549 552 555 558 561 572 575 578 581 584 587 590 593 598 601 604 607 610 613 616 624 627 630 633 636 639 642 645 650 653 656 659 662 665 668 673 676 702 705 708 711 714 717 720 722 728 731 734 737 740 743 754 757 760 763 766 769 772 775 780 783 786 789 792 795 798 806 809 812 815 818 821 824 827 832 835 838 841 844 847 850 855 858 861 864 867 870 873 876 878 884 887 890 893 896 899 907 910 936 938 941 944 947 950 959 962 964 967 970 973 976 979 982 988 990 993 996 999 1002 1005 1014 1016 1019 1022 1025 1028 1031 1034 1040 1042 1045 1048 1051 1054 1057 1063 1066 1068 1071 1074 1077 1080 1083 1086 1092

#include <vector>
#include <iostream>
using namespace std;


struct Trie_node{
    int count;
    Trie_node *children[26];
};
string target = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuyzvwxabcdefghijklmnopqrvwxstuyzabcdefghijklmnopqrvwxyzstuabcdefghijklmnopqryzvwxstughidefjklstumnoabcyzpqrvwxghidefjklstumnovwxabcpqryzghidefjklstumnovwxabcyzpqrghidefjklstumnovwxpqrabcyzghidefjklstumnovwxpqryzabcghidefjklstumnovwxyzpqrabcghidefjklstumnovwxyzabcpqrghidefjklstumnoyzabcvwxpqrghidefjklstumnoyzabcpqrvwxghidefjklstumnoyzvwxabcpqrghidefjklstumnoyzvwxpqrabcghidefjklstumnoyzpqrvwxabcghidefjklstumnoyzpqrabcvwxjklstupqrvwxghimnoabcdefyzjklstupqrvwxghimnoabcyzdefjklstupqrvwxghimnoyzabcdefjklstupqrvwxghimnoyzdefabcjklstupqrvwxghidefmnoabcyzjklstupqrvwxghidefmnoyzabcjklstupqrvwxghidefabcmnoyzjklstupqrvwxghidefabcyzmnojklstupqrvwxghidefyzabcmnostuvwxmnopqrghiabcyzdefjklstuvwxmnopqrghiabcyzjkldefstuvwxmnopqrghidefabcjklyzstuvwxmnopqrghidefabcyzjklstuvwxmnopqrghidefjklabcyzstuvwxmnopqrghidefjklyzabcstuvwxmnopqrghidefyzjklabcstuvwxmnopqrghidefyzabcjklstuvwxmnopqrghiyzabcdefjklyzabcdefghijklvwxmnostupqryzabcdefghijklmnostuvwxpqryzabcdefghijklmnostupqrvwxyzabcdefghijklmnovwxstupqryzabcdefghijklmnovwxpqrstuyzabcdefghijklmnopqrvwxstuyzabcdefghijklmnopqrstuvwx";
vector<string> keys = {"abc", "def", "ghi", "jkl", "mno", "pqr", "stu", "vwx", "yz"};

Trie_node *root;
int len;

Trie_node *create_node(){
    Trie_node *newNode = new Trie_node();
    newNode->count = 0;
    for(int i = 0; i < 26; i++) newNode->children[i] = NULL;
    return newNode;
}

void insert_node(char *key){
    Trie_node *cur = root;
    char *tmp = key;
    while(*tmp){
        if(cur->children[*tmp-'a'] == NULL){
            cur->children[*tmp-'a'] = create_node();
        }
        cur = cur->children[*tmp-'a'];
        tmp++;
    }
    cur->count += 1;
}

bool isOK(int visit[]){
    for(int i = 0; i < keys.size(); i++){
        if(visit[i] == 0) return false;
    }
    return true;
}

void DFS(Trie_node *cur, int pos, int visit[], string curstr){
    if(isOK(visit)){
        cout << pos-len << " ";
        return;
    }
    if(cur->children[target[pos]-'a'] == NULL) return;
    DFS(cur->children[target[pos]-'a'], pos+1, visit, curstr+target[pos]);
    if(cur->children[target[pos]-'a']->count != 0){
                for(int i = 0; i < keys.size(); i++){
            if(keys[i]==curstr+target[pos] && visit[i]==0){
                visit[i] = 1;
                DFS(root, pos+1, visit, "");
                visit[i] = 0;
                return;
            }
        }
    }
}

int main(int argc, char *argv[]){
    len = 0;
    root = create_node();
    for(auto it : keys){
        insert_node(&it[0]);
        len += it.length();
    }
    int *visit = new int[keys.size()];
    for(int i = 0; i <= target.length() - len; i++){
        for(int j = 0; j < keys.size(); j++) visit[j] = 0;
        DFS(root, i, visit, "");
    }
    return 0;
}

比利海灵顿
December 3rd, 2019 at 07:40 pm

@两仪橙
是不是很寂寞

Reply
1. 两仪橙
  December 6th, 2019 at 03:52 pm
  
  @比利海灵顿
  很鸡儿寞
  
  Reply
YH_evIs
November 27th, 2019 at 05:28 pm

@两仪橙
卧槽，碉堡了老铁

Reply