文本嗅探字符串的题

谁借莪１个温暖的怀抱￠ 2022-07-16 03:38 193阅读 0赞

文本嗅探

*  热度指数：670时间限制：3秒空间限制：32768K
 *  本题知识点： [字符串][Link 1]
 *  [ 算法知识视频讲解][Link 2]

## 题目描述 ##

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

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

测试样例：

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

返回：[0,2]

开始想错了，以为是需要按照搜索出现的次数返回数组。。。看了答案，原来只是出现了返回即可，不用按照统计排序。发现用List做会方便很多。。

import java.util.*;
    
    public class KeywordDetect {
        public int[] containKeyword(String[] A, int n, String[] keys, int m) {
            int[] cnt = new int[n];
            for(int i=0;i<n;i++){
                StringBuffer sb =  new StringBuffer(A[i]);
                for(int j=0;j<m;j++){
                    StringBuffer tmp = new StringBuffer(sb);
                    while(tmp.indexOf(keys[j])!=-1){
                        StringBuffer temp=new StringBuffer(tmp.substring(tmp.indexOf(keys[j])+keys[j].length()));
                        cnt[i]++;
                        tmp=temp;
                    }
                }
            }
            int [] tempa = cnt;
            //Arrays.sort(cnt);
            int num=0;
            for(int i=0;i<n;i++){
                if(cnt[i]!=0){
                    num++;
                }  
            }
            if(num==0){
                int[] ret0= new int[1];
                ret0[0]=-1;
                return ret0;
            }
            int[] ret = new int[num];
            int k=0;
            for(int i=0;i<n;i++){
                if(cnt[i]!=0){
                    ret[k++]=i;
                }  
            }
    
            return ret;
        }
    }

别人的答案：

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;
            }
        }
    }

import java.util.*;
     
    public class KeywordDetect {
        public int[] containKeyword(String[] A, int n, String[] keys, int m) {
            // write code here
            TreeSet<Integer> set = new TreeSet<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (A[i].contains(keys[j])) {
                        set.add(i);
                        break;
                    }   
                }
            }   
            if (set.isEmpty()) {
                int[] a = {-1};
                return a;
            }  
            int[] a = new int[set.size()];
            int i = 0;
            for (int pos : set) {
                a[i++] = pos;
            }
            return a;
        }
    }

C++：

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;
        }
    };

[Link 1]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=579
[Link 2]: http://www.nowcoder.com/courses/1