0030_Substring with Concatenation of All Words_未完成_0030.substring with concatenation of all words-程序员宅基地

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

For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]

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

JAVA

方法一

题目的意思是给一个字符串和数组，需要返回一个下标构成的数组，返回的下标的条件是：从每个下标开始，要包含字符串数组中的所有字符串，不考数组中的字符串出现的顺序，且不能包含额外的字符。
第一个想法就是将数组中的字符串做一个全排列，然后在字符串中依次寻找排列后的数组出现的下标。果然超时。。。。

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {        
        List<Integer> result = new ArrayList<Integer>();
        List<Boolean> used = new ArrayList<Boolean>();
        HashSet<Integer> contain = new HashSet<Integer>();
        if(s.length() == 0 || words.length == 0 || words.length * words[0].length() > s.length()){     
            return result;
        }
        for(int i = 0; i < s.length(); ++i){
            used.add(false);
        }
        String target = "";
        getResult(s,words,result,used,target,0,contain);
        return result;
    }
    public void getResult(String s, String[] words,List<Integer> result,List<Boolean> used,String target,int count,HashSet<Integer> contain){
        if(count == words.length){
            int n = s.indexOf(target,0);
            while(n != -1){
                if (!contain.contains(n)){
                    result.add(n);
                    contain.add(n);
                }
                n = s.indexOf(target,n+1);
            }
            return;
        }
        for(int i = 0; i < words.length; ++i){
            if(!used.get(i)){
                used.set(i,true);
                getResult(s,words,result,used,target + words[i],count+1,contain);
                used.set(i,false);
            }
        }
    }
}

方法二

本文链接：https://blog.csdn.net/wsy2846513/article/details/74506603

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

python编码问题之encode、decode、codecs模块_python中encode在什么模块-程序员宅基地

文章浏览阅读2.1k次。原文链接先说说编解码问题编码转换时，通常需要以unicode作为中间编码，即先将其他编码的字符串解码（decode）成unicode，再从unicode编码（encode）成另一种编码。 Eg：str1.decode('gb2312') #将gb2312编码的字符串转换成unicode编码str2.encode('gb2312') #将unicode编码..._python中encode在什么模块

Java数据流-程序员宅基地

文章浏览阅读949次，点赞21次，收藏15次。本文介绍了Java中的数据输入流（DataInputStream）和数据输出流（DataOutputStream）的使用方法。

ie浏览器无法兼容的问题汇总_ie 浏览器 newdate-程序员宅基地

文章浏览阅读111次。ie无法兼容_ie 浏览器 newdate

想用K8s，还得先会Docker吗？其实完全没必要-程序员宅基地

文章浏览阅读239次。这篇文章把 Docker 和 K8s 的关系给大家做了一个解答，希望还在迟疑自己现有的知识储备能不能直接学 K8s 的，赶紧行动起来，K8s 是典型的入门有点难，后面越用越香。

ADI中文手册获取方法_adi 如何查看数据手册-程序员宅基地

文章浏览阅读561次。ADI中文手册获取方法_adi 如何查看数据手册

React 分页-程序员宅基地

文章浏览阅读1k次，点赞4次，收藏3次。React 获取接口数据实现分页效果以拼多多接口为例实现思路加载前加载动画加载后判断有内容的时候无内容的时候用到的知识点1、动画效果（用在加载前，加载之后就隐藏或关闭，用开关效果即可）2、axios请求3、map渲染页面4、分页插件（antd）代码实现import React, { Component } from 'react';//引入axiosimport axios from 'axios';//引入antd插件import { Pagination }_react 分页

随便推点

关于使用CryPtopp库进行RSA签名与验签的一些说明_cryptopp 签名-程序员宅基地

文章浏览阅读449次，点赞9次，收藏7次。这个变量与验签过程中的SignatureVerificationFilter::PUT_MESSAGE这个宏是对应的，SignatureVerificationFilter::PUT_MESSAGE，如果在签名过程中putMessage设置为true，则在验签过程中需要添加SignatureVerificationFilter::PUT_MESSAGE。项目中使用到了CryPtopp库进行RSA签名与验签，但是在使用过程中反复提示无效的数字签名。否则就会出现文章开头出现的数字签名无效。_cryptopp 签名