串联所有单词的子串

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

/**

 * s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

 * 思路：

 * 单词长度为 3

 * 拷贝一份新的 newWords = words

 * 从下标 0 进行递归

 * 找到第一个单词在 newWords 里面的，将该单词在 newWords 移除掉，并进行下次递归，直到 newWords 没值，记录该下标。

 * 下标 + 1

 * 该解法会超时

 *

 */

public class Soultion1 {

    public List<Integer> findSubstring(String s, String[] words) {

        // 每个单词的长度

        int wordLength = words[0].length();

        // 记录满足的下标值

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < s.length(); i++){

            // 拷贝一份新的出来，执行删除操作时不影响原数据

            List<String> newWords = new ArrayList<>(Arrays.asList(words));

            // 如果有效，记录下标值

            if (effective(s, i, wordLength, newWords)){

                result.add(i);

            }

        }

        return result;

    }

    private boolean effective(String s, int pos, int wordLength, List<String> words) {

        // 当 words 为空时，说明该下标满足条件

        if (words.size() == 0) return true;

        // 如果当前下标 + 单词长度超出了总数据长度，则不满足条件

        if (pos + wordLength > s.length()) return false;

        // 当前单词

        String nowWord = s.substring(pos, pos + wordLength);

        // 如果当前单词在 words 里面，进行递归，判断下一个单词是否在剩下的 words 里面

        if (contains(nowWord, words)){

            return effective(s, pos + wordLength, wordLength, words);

        }else {

            return false;

        }

    }

    private boolean contains(String nowWord, List<String> words) {

        for (int i = 0; i < words.size(); i++){

            // 如果在 words 里面，移除该元素

            if (nowWord.equals(words.get(i))){

                words.remove(i);

                return true;

            }

        }

        return false;

    }

}

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.List;

/**

 * s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

 * 思路：

 * 从下标 0 开始，统计第一轮单词组 sList = ["bar","foo","foo"]

 * 如果 sList 与 words 内容相同，记录该下标

 * 下标 + 1

 * 该解法刚好通过

 */

public class Soultion2 {

    public List<Integer> findSubstring(String s, String[] words) {

        // 每个单词的长度

        int wordLength = words[0].length();

        // 记录满足的下标值

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < s.length(); i++){

            // 拷贝一份新的出来，执行删除操作时不影响原数据

            List<String> newWords = new ArrayList<>(Arrays.asList(words));

            // 如果有效，记录下标值

            if (effective(s, i, wordLength, newWords)){

                result.add(i);

            }

        }

        return result;

    }

    private boolean effective(String s, int pos, int wordLength, List<String> words) {

        // 如果当前下标 + words 里面单词所有的长度超过数据长度，则不满足要求

        if (pos + words.size() * wordLength > s.length()) return false;

        // 记录 pos 到 pos + words.size () * wordLength 的数据

        List<String> sList = new ArrayList<>();

        for (int i = 0; i < words.size(); i++){

            sList.add(s.substring(pos + i * wordLength, pos + (i + 1) * wordLength));

        }

        // 将当前截取长度进行排序

        Collections.sort(sList);

        // 将 words 进行排序

        Collections.sort(words);

        // 如果两者相等，则满足要求

        if (sList.equals(words)){

            return true;

        }else {

            return false;

        }

    }

}

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

/**

 * s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

 * 思路：

 * 第一轮单词为 bar,foo,foo

 * 将 words 转为 map = {"bar": 1,"foo": 1,"the": 1}

 * 如果当前单词在 map 中，数量减一，如果数量为零，则将该单词在 map 中移除掉

 * 如果 map 中无单词，说明当前下标满足要求

 * 下标 + 1

 * 该解法要比上面快一点点

 */

public class Soultion3 {

    public List<Integer> findSubstring(String s, String[] words) {

        // 每个单词的长度

        int wordLength = words[0].length();

        // 记录满足的下标值

        List<Integer> result = new ArrayList<>();

        // 将数组转换成 map 的形式

        Map<String, Integer> mapWords = convertToMap(words);

        for (int i = 0; i < s.length(); i++){

            // 拷贝一份新的出来，执行删除操作时不影响原数据

            Map<String, Integer> newWords = new HashMap<>(mapWords);

            // 如果有效，记录下标值

            if (effective(s, i, wordLength, newWords, words.length)){

                result.add(i);

            }

        }

        return result;

    }

    private Map<String, Integer> convertToMap(String[] words) {

        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < words.length; i++){

            if (map.containsKey(words[i])){

                map.put(words[i], map.get(words[i]) + 1);

            }else {

                map.put(words[i], 1);

            }

        }

        return map;

    }

    private boolean effective(String s, int pos, int wordLength, Map<String, Integer> words, int length) {

        // 如果当前下标 + words 里面单词所有的长度超过数据长度，则不满足要求

        if (pos + length * wordLength > s.length()) return false;

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

            // 当前单词

            String substring = s.substring(pos + i * wordLength, pos + (i + 1) * wordLength);

            // 如果当前单词在 words 中，并且数量大于 1，将数量减 1

            // 否则将该单词在 words 中移除

            if (words.containsKey(substring)){

                Integer number = words.get(substring);

                if (number - 1 == 0) words.remove(substring);

                else words.put(substring, number - 1);

            }else {

                return false;

            }

        }

        // 如果 words 中单词都不存在，则说明满足要求

        return words.isEmpty();

    }

}