This is the 27th day of my participation in Gwen Challenge

preface

The substrings of all the words in question 30 are as follows:.

Given a string s and some words of the same length. Find the starting position of the substring in S that happens to be formed by concatenating all the words in words.

Note that the substring must match exactly the words in words, without any other characters in the middle, but you do not need to consider the sequence in which words are concatenated.

Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”] Output: [0,9] Explanation: Substrings starting from index 0 and 9 are “barfoo” and “foobar”, respectively. The order of the outputs is not important, [9,0] is also a valid answer.

Example 2:

Input: s = “wordgoodGoodGoodBestWord “, words = [“word”,”good”,”best”,”word”] output: []

Example 3:

Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”] output: [6,9,12]

A, thinking

There are two important pieces of information in the question: words of the same length and you don’t need to worry about the sequence of words

I did it using a hash table, but the beat rate was not very good. So look at the buckle above the use of sliding window + hash table can be effectively optimized, beat rate can reach 98%. After looking at other people’s solutions, I plan to implement a shorter method of my own, without AC, and wait for the implementation of plan 2.

Here we mainly talk about the use of hash table to achieve, the approximate steps are as follows:

  1. Place the words in the hash table before each iteration
  2. Determines whether the string from the current position matches the words exactly, and if it does, adds it to the result

For example

If the key exists in the map, value -1 is used

Using example 1 as an example, the starting point is I =0

  1. Create a hash table map where key is the word and value is the number of occurrences of the word. The result here is zero{'foo': 1; 'bar': 1}
  2. Takes the length of one word from a stringbar, change map, at this timebar -> 0.
  3. Take the length of a wordfoor, change map, at this timefoor -> 0.
  4. It can match and is added to the result set RET0
  5. The other positions are similar

Second, the implementation

The implementation code

WordLen: word array length wordLen: word array length map: temporary hash table. Value is the number of occurrences of a word

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        int len = words.length; // Array length
        int wordLen = words[0].length();
        for (int i=0; i< s.length() - len * wordLen + 1; i++)  {
            Map<String, Integer> map = new HashMap<>();
            // Put it in a HashMap
            for (String word : words) {
                map.merge(word, 1, Integer::sum);
            }
            for (int j=0; j < len; j++) {
                String word = s.substring(i + j * wordLen, i + (j+1) * wordLen);
                if (map.containsKey(word) && map.get(word) > 0) {
                    map.merge(word, -1, Integer::sum);
                    if (j == len -1) { ret.add(i); }}else {
                    break; }}}return ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        String[] words = {"word"."good"."best"."good"};
        new Number30().findSubstring("wordgoodgoodgoodbestword", words);
    }
Copy the code

The results of

Third, summary

Beat rate is still not quite ideal, and so on to achieve a better way to update plan 2!

Thank you to see the end, very honored to help you ~♥