030 Substring with Concatenation of All Words 与所有单词相关联的字串

给定一个字符串 s 和一些长度相同的单词 words，找出 s 与 words 中所有单词（words 每个单词只出现一次）串联一起（words中组成串联串的单词的顺序随意）的字符串匹配的所有起始索引，子串要与串联串完全匹配，中间不能有其他字符。
举个例子，给定：
s："barfoothefoobarman"
words：["foo", "bar"]
你应该返回的索引: [0,9]。（任意顺序）
详见：https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

Java实现：

class Solution {

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

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

        if(s.isEmpty()||s==null||words==null||words.length==0){

            return res;

        }

        int n=words.length;

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

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

        for(String str:words){

            if(m1.containsKey(str)){

                m1.put(str,m1.get(str)+1);

            }else{

                m1.put(str,1);

            }

        }

        for(int i=0;i<=s.length()-n*m;++i){

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

            int j=0;

            for(;j<n;++j){

                String t=s.substring(i+j*m,i+j*m+m);

                if(!m1.containsKey(t)){

                    break;

                }

                if(m2.containsKey(t)){

                    m2.put(t,m2.get(t)+1);

                }else{

                    m2.put(t,1);

                }

                if(m2.get(t)>m1.get(t)){

                    break;

                }

            }

            if(j==n){

                res.add(i);

            }

        }

        return res;

    }

}

参考：https://www.cnblogs.com/grandyang/p/4521224.html

https://blog.csdn.net/fly_yr/article/details/47957459

巴特西

030 Substring with Concatenation of All Words 与所有单词相关联的字串

最新文章

热门文章