现在有一个字符串列表,和一个关键词列表,请设计一个高效算法,检测出含关键字列表中关键字(一个或多个)的字符串。
给定字符串数组A及它的大小n以及关键词数组key及它的大小m,请返回一个排好序的含关键词的字符串序号的列表。保证所有字符串长度小于等于100,关键词个数小于等于100,字符串个数小于等于200。保证所有字符串全部由小写英文字符组成。若不存在含关键字的字符串,请返回一个只含-1的数组。
现在有一个字符串列表,和一个关键词列表,请设计一个高效算法,检测出含关键字列表中关键字(一个或多个)的字符串。
给定字符串数组A及它的大小n以及关键词数组key及它的大小m,请返回一个排好序的含关键词的字符串序号的列表。保证所有字符串长度小于等于100,关键词个数小于等于100,字符串个数小于等于200。保证所有字符串全部由小写英文字符组成。若不存在含关键字的字符串,请返回一个只含-1的数组。
["nowcoder","hello","now"],3,["coder",now],2
[0,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; } }
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
}
};
直接暴力求解就好! 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; } };
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;
/* 双循环查找,如果发现存在,就加入数组中,如果都没有,返回-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; } } }
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; } };
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; }
importjava.util.*;publicclassKeywordDetect {publicint[] containKeyword(String[] A, intn, String[] keys, intm) {// write code hereintnum=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;}}
没想出什么好的办法,直接暴力了。
};
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; }
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; } } }
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; } }
两层循环遍历字符串数组与关键词数组,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; } }
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; } };