首页 > 试题广场 >

子串判断

[编程题]子串判断

热度指数：6733 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个string数组p及其大小n，同时给定长字符串string s，请返回一个bool数组，元素为true或false对应p中的对应字符串是否为s的子串。要求p中的串长度小于等于8，且p中的串的个数小于等于500，同时要求s的长度小于等于1000。

测试样例：

["a","b","c","d"],4,"abc"

返回：[true,true,true,false]

算法知识视频讲解

王六六

class Substr:
    def chkSubStr(self, p, n, s):
        # write code here
        yes=set()
        no=set()
        ans=[]
        for w in p:
            if w in yes:
                ans.append(True)
            elif w in no:
                ans.append(False)
            else:
                if w in s:
                    yes.add(w)
                    ans.append(True)
                else:
                    no.add(w)
                    ans.append(False)
        return ans

这种方法略快于暴力判断

发表于 2019-06-28 16:47:42 回复(0)

更多回答

念润

思路：

直接利用string的find函数,即可判断是否在给定的字符串中。

代码：

class Substr {
public:
    vector<bool> chkSubStr(vector<string> p, int n, string s) {
        vector<bool> result;
        for(int i = 0;i < n;++i){
            if(s.find(p[i]) != -1){
                result.push_back(true);
            }//if
            else{
                result.push_back(false);
            }//else
        }//for
        return result;
    }
};

发表于 2015-08-12 22:15:15 回复(0)

Python

华科平凡

python one line solution

return map(lambda c:c in s,p)

发表于 2017-10-01 22:49:36 回复(0)

revivedSuN

复习trie树

class Substr {
public:
    struct TrieNode{
        char c;
        struct TrieNode* ptr[26];
        TrieNode(char c):c(c){
            memset(ptr,0,sizeof(ptr));
        }
    };
    void insert(TrieNode *&root,const string &str,int i){
        if(i >= str.size()){
            return;
        }
        int index = str[i] - 'a';
        if(root->ptr[index] == NULL){
            root->ptr[index] = new TrieNode(str[i]);
            cout<<str[i];
            if(i == str.size() - 1){
                return;
            }
        }
        insert(root->ptr[index],str,i+1);
    }
    bool findSub(TrieNode *root,const string &str){

        for(int i = 0; i < str.size(); i++){
            TrieNode *node = root->ptr[str[i]-'a'];
            if(node == NULL || node->c != str[i])
                return false;
            root = root->ptr[str[i]-'a'];
        }
        return true;
    }
    void build(TrieNode *&root,const string& str){
        for(int i = 0; i < str.size(); i++){
            insert(root,str,i);
            cout<<endl;
        }

    }
    vector<bool> chkSubStr(vector<string> p, int n, string s) {
        vector<bool> vec;
        if(p.size() < 1) return vec;
        TrieNode* root = new TrieNode(0);
        build(root,s);
        for(int i = 0; i < p.size(); i++){
            if(findSub(root,p[i])){
                vec.push_back(true);
            }else{
                vec.push_back(false);
            }
        }
        return vec;
    }
};

发表于 2015-08-23 16:41:29 回复(2)

呜呜呜

    public boolean[] chkSubStr(String[] p, int n, String s) {
        boolean[] res = new boolean[n];
        for (int i = 0; i < n; i++) {
            res[i] = s.contains(p[i]);
        }
        return res;
    }

发表于 2016-12-16 14:15:55 回复(0)

幻之飞雪

trie树java版本。

import java.util.*;
public class Substr {
    
    void insert(Node root,String str,int i){
    	if(i>=str.length())
    		return;
    	int index=str.charAt(i)-'a';
    	if(root.children[index]==null){
    		root.children[index]=new Node(str.charAt(i));
    		if(i==str.length()-1)
    			return;
    	}
    	insert(root.children[index], str, i+1);
    }
    
    boolean findSub(Node root,String str){
    	for(int i=0;i<str.length();++i){
    		Node node=root.children[str.charAt(i)-'a'];
    		if(node==null||node.c!=str.charAt(i))
    			return false;
    		root=root.children[str.charAt(i)-'a'];
    	}
    	return true;
    }
    
    void build(Node root,String str){
    	for(int i=0;i<str.length();++i){
    		insert(root, str, i);
    	}
    }
    
    public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
        boolean[] re=new boolean[n];
        if(p.length<1)
        	return re;
        Node root=new Node('0');
        build(root, s);
        for(int i=0;i<p.length;++i){
        	if(findSub(root, p[i]))
        		re[i]=true;
        	else {
				re[i]=false;
			}
        }
        return re;
    }
}


class Node {
	private static final int D_size=26;
	
	protected char c;
	protected Node[] children=new Node[D_size];
	
	Node(char c){
		this.c=c;
	}
}

编辑于 2016-06-14 19:52:03 回复(0)

Java

蓝胖子SHD

import java.util.*;

public class Substr {
    public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
         boolean[]hasSub=new boolean[p.length];
		 for (int i = 0; i < p.length; i++) {
			hasSub[i]=s.contains(p[i]);
		}
		 return hasSub;
    }
}

编辑于 2016-08-13 15:02:21 回复(0)

Python

QuestCompleted

class Substr:
    def chkSubStr(self, p, n, s):
        # write code here
        return [i in s for i in p]

发表于 2016-12-28 14:13:56 回复(0)

峰峰的牛客

//记得换一下类名
import java.util.*;

public class Main1 {
    public boolean[] chkSubStr(String[] p, int n, String s) {
        boolean[] arr=new boolean[n];
        /**这里这么判断行倒是行，但是是O(n^2)复杂度呀
        for(int x=0;x<arr.length;x++){
            for(int i=0;i<p.length;){
                if(s.contains(p[i])){
                    arr[x]=true;
                }else {
                    arr[x]=false;
                }
            }
        }*/
        //因为s.contains本来返回的就是Boolean类型的值，所以直接赋值
        //这里的因为这里的p.length==n，所以就不用放在新的for循环里
        for (int i = 0; i < n; i++) {
            arr[i] = s.contains(p[i]);
        }
        return arr;
    }
}

发表于 2019-11-27 15:17:39 回复(0)

ID84848484

import java.util.*;

public class Substr {
    public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
        boolean[] ret=new boolean[n];
        for(int i=0;i<n;i++){
            ret[i]=s.contains(p[i]);
        }
        return ret;
    }
}

发表于 2019-05-26 22:27:15 回复(1)

aud

// 大概是最容易想到的方法了
import java.util.*;

public class Substr {
    public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
        boolean[] res = new boolean[n];
        for(int i=0;i<p.length;i++)
        {
            res[i] = isSubStr(p[i],s);
        }
        return res;
    }
    
    public boolean isSubStr(String sub,String s)
    {
        if(s.indexOf(sub) != -1)
            return true;
        else
            return false;
    }
}

发表于 2019-01-27 01:13:11 回复(0)

Cavs

记录每个字符出现的位置，子串从该位置开始比较
#include<unordered_map>
#include<unordered_set>
class Substr{
public:
	vector<bool> chkSubStr(vector<string> p, int n, string s)
	{
		vector<bool> res(n, false);
		unordered_map<char, unordered_set<int>> place;
		for (int i = 0; i < s.size(); ++i)
		{
			place[s[i]].emplace(i);
		}

		for (int i = 0; i < n; ++i)
		{
			string str = p[i];
			if (place.find(str[0]) != place.end())
			{
				for (auto& pos : place[str[0]])
				{
					if (pos + str.size() - 1 < s.size() &&
						s.substr(pos, str.size()) == str)
					{
						res[i] = true;
						break;
					}
				}
			}
		}

		return res;
	}
};

发表于 2017-07-02 17:53:43 回复(0)

Aurora1

class Substr:
    def chkSubStr(self, p, n, s):
        root = Node()
        for i in range(len(s)):
            root.insert(s[i:])
        return [root.search(x) for x in p]


class Node: #后缀树
    def __init__(self):
        self.child = {}

    def insert(self, s):
        if len(s) > 0:
            c = s[0]
            if c in self.child:
                n = self.child[c]
            else:
                n = Node()
                self.child[c] = n
            n.insert(s[1:])

    def search(self, s):
        if len(s) == 0:
            return True
        c = s[0]
        if c in self.child:
            return self.child[c].search(s[1:])
        return False

发表于 2017-03-20 14:14:31 回复(0)

Top_bo

java 语言实现：

public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
		boolean check[]=new boolean[n];
		if(p==null||s==null)
			return check;
		for(int i=0;i<p.length;i++){
			if(s.contains(p[i])){
				check[i]=true;
			}else{
				check[i]=false;
			}
		}
		return check;
    }

发表于 2015-09-06 00:33:38 回复(0)

yefengzhichen

自己实现的Java版本字典查找树，以前只有概念没看过代码。。可能会略显复杂= =

import java.util.*;

class Node {
    Character ch;
    Map<Character, Node> map;
    
    public Node(Character ch) {
        this.ch = ch;
        map = new HashMap<Character, Node>();
    } 
    //方便对map进行操作，因此进行了重写。。不然每次都得多加.map。
    public boolean containsKey(Character ch){
        return map.containsKey(ch);
    }    
    public Node get(Character ch){
        return map.get(ch);
    }
    public Node put(Character ch, Node node){
        return map.put(ch, node);
    }
}

public class Substr { 
    public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
        Node root = new Node('0');
        List<Node> list = new ArrayList<>();
        int len = s.length();
        //建树
        for(int i = 0; i < len; i++) {
            int oldSize= list.size();
            char key = s.charAt(i);
            //列表保存每一步达到的节点，下一次会从这些位置开始，再加上从root开始查找
            List<Node> newList = new ArrayList<>();
            for(int j = 0; j < oldSize; j++) {
               Node node = list.get(j);
               if(node.containsKey(key)) {
                   newList.add(node.get(key));
               } else {
                   Node child = new Node(key);
                   node.put(key, child);
                   newList.add(node.get(key));
               }
            }
            //从root开始查找 if(root.containsKey(key)){
                newList.add(root.get(key));
            } else {
                Node child = new Node(key);
                root.put(key, child);
                newList.add(root.get(key));
            }
            list = newList;
        }
        boolean[] resu = new boolean[n];
        for(int i = 0; i < n; i++) {
            String str = p[i];
            Node node = root;
            boolean flag = true;
            for(int j = 0; j < str.length(); j++) {
                char key = str.charAt(j);
                if(node.containsKey(key)) {
                    node = node.get(key);
                } else {
                    flag = false;
                    break;
                }
            }
            resu[i] = flag;
        }
        return resu;
    }
    
}

发表于 2016-08-26 19:45:09 回复(1)

Java

牛客466700261号

public class Substr {
    public boolean[] chkSubStr(String[] p, int n, String s) {
        boolean[] f=new boolean[n];
        for(int i=0;i<n;i++){
            f[i]=s.indexOf(p[i])>=0?true:false;
        }
        return f;
    }
}

发表于 2021-11-27 13:04:54 回复(0)

寒星星

# -*- coding:utf-8 -*-

class Substr:
def chkSubStr(self, p, n, s):
res=[]
for i in p:
if i in s:
res.append(True)
else:
res.append(False)
return res

发表于 2021-03-04 14:25:17 回复(0)

cl、

判断s中是否存在p[i]即可

import java.util.*;

public class Substr {
    public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
        boolean[] bool = new boolean[n];// 默认为false
        for(int i=0;i<n;i++){
            if(s.indexOf(p[i])>-1){
                bool[i] = true;
            }
        }
        return bool;
    }
}

发表于 2020-10-26 14:35:35 回复(0)

我是ben啊

第一个想到的就是字典树但是实现起来很复杂，然后为了减少比较次数加上字符串都是小写我们可以用空间换时间，通过2维数组记录每个字母出现的位置通过索引去一一比较。

public static boolean[] chkSubStr(String[] p, int n, String s) {
        //记录26个字母出现的位置
		ArrayList<Integer>[] lists= new ArrayList[26];
		for (int i = 0; i < lists.length; i++) {
			lists[i]=new ArrayList<>();
		}
		 int i=0;
		 int pos=0,z=0,q=0,length=0;
		 boolean flag=false;
		 while(i<s.length()) {
			 q=s.charAt(i)-97;
			 lists[q].add(i);
			 i++;
		 }
		 boolean[] bs=new boolean[p.length];
		 for (int j = 0; j < p.length; j++) {
			pos=p[j].charAt(0)-97;
			z=0;
			flag=false;
			length=p[j].length();
             //根据2维数组记录的位置通过substring进行比较
			while(flag==false&&z<lists[pos].size()) {
				if (s.substring(lists[pos].get(z),Math.min(lists[pos].get(z)+length, s.length())).equals(p[j])) {
					flag=true;
				}
				z++;
			}
			bs[j]=flag;
		}
		return bs;
	    }

发表于 2020-06-18 17:26:09 回复(0)

Java

只吃五顿饭

import java.util.*;

public class Substr {
    public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
        boolean[] result = new boolean[n];
        for (int i = 0; i < n; i++) {
            result[i] = s.contains(p[i]);
        }
        return result;
    }
}

发表于 2020-06-08 10:14:24 回复(0)

復活の検事

import java.util.*;

public class Substr {
    public boolean[] chkSubStr(String[] p, int n, String s) {
        boolean[] result = new boolean[n];
        for (int i=0;i<n;i++) {
            if(s.contains(p[i])){
                result[i] = true;
            }else{
                result[i] = false;
            }
        }
        return result;
    }
}

发表于 2020-04-17 23:39:10 回复(0)