首页 > 试题广场 >

文本嗅探

[编程题]文本嗅探
  • 热度指数:7632 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

现在有一个字符串列表,和一个关键词列表,请设计一个高效算法,检测出含关键字列表中关键字(一个或多个)的字符串。

给定字符串数组A及它的大小n以及关键词数组key及它的大小m,请返回一个排好序的含关键词的字符串序号的列表。保证所有字符串长度小于等于100,关键词个数小于等于100,字符串个数小于等于200。保证所有字符串全部由小写英文字符组成。若不存在含关键字的字符串,请返回一个只含-1的数组。


示例1

输入

["nowcoder","hello","now"],3,["coder",now],2

输出

[0,2]
暂且不说我会不会做这题目,但看得出来 出题人的语文水平不高,做事的责任心不够。
发表于 2017-01-03 15:13:11 回复(2)

python解法来装个b,只需要两行

class KeywordDetect:
    def containKeyword(self, A, n, keys, m):
        res={i for i,v in enumerate(A) for key in keys if key in v}
        return list(res) if res else [-1]
发表于 2017-11-07 17:33:28 回复(2)
import java.util.*;

public class KeywordDetect {
    public int[] containKeyword(String[] A, int n, String[] keys, int m) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0;i<n;i++){
        	for(int j = 0;j<m;j++){
        		if(A[i].indexOf(keys[j])>-1){
        			list.add(i);
        			break;
        		}
        	}
        }
        if(list.isEmpty())
        	return new int[]{-1};
        int[] r = new int[list.size()];
        for(int i = 0;i<list.size();i++)
        	r[i] = list.get(i);
        return r;
        
    }
}

编辑于 2016-04-14 15:29:26 回复(5)
萌头像
如果把A拼接成一个大的string,效果会不会更好?
发表于 2016-05-04 11:38:13 回复(3)

class KeywordDetect {
public:
vector<int> containKeyword(vector<string> A, int n, vector<string> keys, int m) {
string temp;
string temp1;
vector<int>B;
int k=0;

    for(int i=0;i<m;i++)
        {
        temp=keys[i];
        for(int j=0;j<n;j++)
            {
            temp1=A[j];
            string::size_type idx;
            idx=temp1.find(temp);
            if(idx!=string::npos)
                {
               B.push_back(j);
                k++;
    //            break;
            }
        }
    }
    if(k==0)
        {
        B.push_back(-1);
    }
    sort(B.begin(),B.end());

     B.erase(unique(B.begin(), B.end()), B.end());
    return B;
    // write code here
}

};

发表于 2017-07-17 10:52:47 回复(0)
直接暴力求解就好!
class KeywordDetect {
public:
    bool contain(string s1,string s2)
    {
    	 for(int i=0;i<s1.size()-s2.size()+1;i++)
         {
             string tmp=s1.substr(i,s2.size());
             if(tmp==s2)
                 return true;
         }
         return false;
    }   
    vector<int> containKeyword(vector<string> A, int n, vector<string> keys, int m) {
        vector<int> res;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(contain(A[i],keys[j]))
                {
                    res.push_back(i);
                    break;
                }
            }
        }
        if(res.size()==0)
            res.push_back(-1);
        return res;
    }
};

发表于 2017-07-02 19:54:50 回复(0)
class KeywordDetect:
    def containKeyword(self, A, n, keys, m):
        r =[]
        for i in range(n):
            for k in keys:
                if k in A[i]:
                    r.append(i)
                    break
        return r if r else [-1]

发表于 2017-06-26 21:22:33 回复(0)
class KeywordDetect {
public:
    vector<int> containKeyword(vector<string> A, int n, vector<string> keys, int m) {
        vector<int>ve;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(A[i].find(keys[j])!=-1){
                    ve.push_back(i);break;
                }
            }
        }
        if(!ve.empty())return ve;
        ve.push_back(-1);return ve; 
    

发表于 2017-02-27 19:29:22 回复(0)
/*
双循环查找,如果发现存在,就加入数组中,如果都没有,返回-1
*/
import java.util.*;

public class KeywordDetect {
    public static int[] containKeyword(String[] A, int n, String[] keys, int m) {
		StringBuffer sb = new StringBuffer(); 
		for(int i=0;i<A.length;i++){
			for(int j=0;j<keys.length;j++){
				if(A[i].indexOf(keys[j]) != -1){
					sb.append(i).append(",");
					break;
				}
			}
		}
		if(sb.toString().equals("")){
			int[] s = {-1};
			return s;
		}else{
			String[] strings = sb.toString().split(",");
			int[] result = new int[strings.length];
			for(int i=0;i<result.length;i++){
				result[i] = Integer.parseInt(strings[i]);
			}
			return result;
		}
	}
}

发表于 2016-09-18 22:36:49 回复(1)
class KeywordDetect {
public:
    vector<int> containKeyword(vector<string> A, int n, vector<string> keys, int m) {
        vector<int> vec;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            	if(A[i].find(keys[j])!=string::npos){
            		vec.push_back(i);
            		break;
        		}
        if(vec.empty())
            vec.push_back(-1);
        return vec;
    }
};

发表于 2016-09-03 09:14:19 回复(0)
Naive 查找,逐个搜索,不知道有没有更好的方法

    vector<int> containKeyword(vector<string> A, int n, vector<string> keys, int m) {
        vector<int> ans;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            	if(A[i].find(keys[j]) != string::npos)
            	{
            		ans.push_back(i);
            		break;
        		}
        if(ans.empty())
            ans.push_back(-1);
        return ans;
    }

发表于 2016-08-29 11:33:50 回复(2)
importjava.util.*;
publicclassKeywordDetect {
    publicint[] containKeyword(String[] A, intn, String[] keys, intm) {
        // write code here
        intnum=0;
         List<Integer> list=newArrayList<Integer>();
         for(inti=0;i<n;i++){
             for(intj=0;j<m;j++){
                 if(A[i].contains(keys[j])){                                list.add(i);
                     num++;
                     break;//如果字符串列表含有关键字就跳出结束循环,继续下次循环
                 }                 
             }
         }
         int[] res=newint[num];
         if(num==0)
             returnnewint[]{-1};
         for(intj=0;j<list.size();j++){
             res[j]=list.get(j);
         }
        returnres;
    }
}

编辑于 2015-10-17 09:06:19 回复(5)
没想出什么好的办法,直接暴力了。
classKeywordDetect {
public:
    vector<int> containKeyword(vector<string> A, intn, vector<string> keys, intm) {
        // write code here
        vector<int>vec;
        for(inti=0;i<n;++i)
        {
            for(intj=0;j<m;++j)
            {
                if(A[i].find(keys[j])!=-1)
                {
                    vec.push_back(i);
                    break;
                }
            }
        }
        if(vec.size()==0) vec.push_back(-1);
        returnvec;
    }
};

发表于 2015-10-13 19:09:12 回复(1)
vector<int> containKeyword(vector<string> A, int n, vector<string> keys, int m) {
        // write code here
        vector<int> v;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j)
                if(A[i].find(keys[j]) != string::npos){
                v.push_back(i);
                break;
            }
        }
        if(v.empty())
            v.push_back(-1);
        return v;
    }
发表于 2016-03-08 20:27:18 回复(0)
暴力法解决,还能怎么高效
import java.util.*;

public class KeywordDetect {
    public int[] containKeyword(String[] A, int n, String[] keys, int m) {
        // write code here
        boolean[] used = new boolean[n];
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++)
                if(A[i].contains(keys[j]) && !used[i]) {
                    list.add(i);
                    used[i] = true;
                }
        }
        if(list.isEmpty())
            return new int[]{-1};
        else{
            int[] res = new int[list.size()];
            for(int i = 0; i < list.size(); i++) res[i] = list.get(i);
            return res;
        }
    }
}

发表于 2021-04-09 11:39:59 回复(0)
import java.util.*;

public class KeywordDetect {
    public int[] containKeyword(String[] A, int n, String[] keys, int m) {
        // write code here
        List<Integer> list = new ArrayList();
        // 循环遍历筛选符合条件的关键词,将下标添加到数组中
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (A[i].indexOf(keys[j]) != -1) {
                    list.add(i);
                    break;
                }
            }
        }

        // 不存在关键字符串,返回-1
        if (list.size() == 0) {
            list.add(-1);
        }

        // 将list集合转为int数组
        int[] res = new int[list.size()];
        for (int i=0; i<list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

发表于 2023-02-14 19:18:42 回复(0)
import java.util.*;
import java.util.stream.Collectors;
public class KeywordDetect {
    public int[] containKeyword(String[] A, int n, String[] keys, int m) {
      List<Integer> list = new ArrayList<>();
        for (int i = 0; i < A.length; i++) {
            for (String s : keys) {
                if (A[i].contains(s)) {
                    list.add(i);
                }
            }
        }
        if (list.size() == 0) {
            list.add(-1);
        }
        int[] result = list.stream().distinct().sorted().mapToInt(x -> x).toArray();
        return result;
    }
}
发表于 2022-01-06 16:35:52 回复(0)
class KeywordDetect {
public:
    vector<int> containKeyword(vector<string> A, int n, vector<string> keys, int m) {
        vector<int>a;
        set<int>s;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(A[j].find(keys[i])!=-1)
                {
                    a.push_back(j);
                    
                }
            }
        }
        sort(a.begin(),a.end());
        for(int i=0;i<a.size();i++)s.insert(a[i]);
        a.clear();
        for(set<int>::iterator it=s.begin();it!=s.end();it++)a.push_back(*it);
        if(a.size()==0)a.push_back(-1);
        return a;
    }
};
发表于 2020-09-18 11:22:00 回复(0)

两层循环遍历字符串数组与关键词数组,List来存储字符串数组中包含关键词的位置,注意判断重复的情况。比如nowcoder包含coder、now两个关键词,此时就要注意避免重复将这个词所对应的位置添加到List中去。

import java.util.*;

public class KeywordDetect {
    public int[] containKeyword(String[] A, int n, String[] keys, int m) {
          List<Integer> list = new ArrayList();
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){//关键词
                String str = A[i].replace(keys[j], "");// 单个单词包含关键词
                if (str.length() < A[i].length()){
                    if (!list.contains(i))
                        list.add(i);
                }
            }
        }
        int[] res = new int[list.size()];
        for (int index = 0; index < list.size(); index++) {
            res[index] = list.get(index);
        }
        if (res.length == 0)
            return new int[] {-1};
        return res;
    }
}
发表于 2019-09-08 11:15:15 回复(0)
虽然很简单,但是渣渣还是会因为AC而开心的😊
class KeywordDetect {
public:
    vector<int> containKeyword(vector<string> A, int n, vector<string> keys, int m) {
        // write code here
        vector<bool> flag(n,false);
        vector<int> index;
        for(int i=0;i<m;i++)
        {
            string key=keys[i];
            for(int j=0;j<n;j++)
            {
                string str=A[j];
                if(str.find(key)!=string::npos)
                {
                    flag[j]=true;
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            if(true==flag[i])
            {
                index.push_back(i);
            }
        }
        if(index.empty())
        {
            index.push_back(-1);
        }
        return index;
    }
};

发表于 2019-04-11 22:39:25 回复(0)

问题信息

难度:
77条回答 18272浏览

热门推荐

通过挑战的用户

查看代码