首页 > 代码库 > leetcode--Substring with Concatenation of All Words

leetcode--Substring with Concatenation of All Words

2024-07-06 07:29:51   222人阅读

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

 

Have you been asked this question in an interview? 

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class Solution{ 
    public static List<Integer> findSubstring(String S, String[] L){
        ArrayList<Integer> startPoints = new ArrayList<Integer>();
        if(L.length != 0){
            if(S== null || S.length() == 0)
                return startPoints;
            else{
                int lengthOfArray = L.length;
                int lengthOfWord = L[0].length();
                int lengthOfString = S.length();
                if(lengthOfString < lengthOfArray * lengthOfWord)
                    return startPoints;
                else{
                    //put the string[] into a dict
                    Map<String, Integer> dict = new HashMap<String, Integer>();
                    for(int j = 0; j < lengthOfArray; ++j){
                        if(dict.containsKey(L[j])){
                            int value = http://www.mamicode.com/dict.get(L[j]) + 1;
                            dict.put(L[j], value);
                        }
                        else
                            dict.put(L[j], 1);
                    }
                     
                    for(int i = 0; i < lengthOfString - lengthOfWord * lengthOfArray + 1; ++i){
                        //check each substring with length lengthOfWord * lengthOfArray starting from index i
                        Map<String, Integer> check = new HashMap<String, Integer>();
                        boolean canBeStart = true;
                        for(int j = 0; j < lengthOfArray; ++j){
                            String inChecked = S.substring(i + j * lengthOfWord, i + (j + 1)*lengthOfWord);
                            if(dict.containsKey(inChecked)){
                                if(check.containsKey(inChecked)){
                                    int mult = check.get(inChecked) + 1;
                                    if(mult > dict.get(inChecked)){
                                        canBeStart = false;
                                        break;
                                    }
                                    else
                                        check.put(inChecked, mult);                                    
                                }
                                else
                                    check.put(inChecked, 1);
                            }
                            else{
                                canBeStart = false;
                                break;
                            }
                        }                      
                        if(canBeStart)
                            startPoints.add(i);                    
                    }
                }
            }          
        }
        return startPoints;
    }
}

　　


联系
我们