网站建设绩效考核,访问的网站显示建设中,齐家网装修口碑怎么样,商场的平面设计主要做什么题目#xff1a;
给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串#xff0c;可以从中删去一些字符(可以是none)#xff0c;而不改变其余字符的相对顺序。
例如#xff0c; “ace” 是 “…题目
给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串可以从中删去一些字符(可以是none)而不改变其余字符的相对顺序。
例如 “ace” 是 “abcde” 的子序列。
示例 1:
输入: s abcde, words [a,bb,acd,ace]
输出: 3
解释: 有三个是 s 的子序列的单词: a, acd, ace。
Example 2:
输入: s dsahjpjauf, words [ahjpjau,ja,ahbwzgqnuk,tnmlanowax]
输出: 2
代码
import java.util.ArrayList;
import java.util.List;class Solution1 {public static void main(String[] args) {String s abcde;String[] words {a,bb,acd,ace};System.out.println(numMatchingSubseq(s, words));}public static int numMatchingSubseq(String s, String[] words) {// 创建一个数组用于存放26个英文字母的位置ListInteger[] pos new List[26];for(int i 0; i 26; i){pos[i] new ArrayListInteger(); // 初始化每个字母位置的列表}for(int i 0; i s.length(); i){pos[s.charAt(i) - a].add(i);}// 初始化最终结果 int res words.length;for(String w : words){if(w.length() s.length()){res--;continue;}int p -1;// 用于记录上一个字符在S中出现的位置for(int i 0; i w.length(); i){char c w.charAt(i);// 如果当前字符c在s中没有出现或者c在s中最后出现的位置不大于p则w不是s的子序列if(pos[c-a].isEmpty() || pos[c-a].get(pos[c - a].size()-1) p ){res--;break;}p binarySearch(pos[c - a], p);}}return res;}public static int binarySearch(ListInteger list, int tagert){int left 0;int right list.size()-1;while(left right){int mid (left right)/2;if(list.get(mid) tagert){left mid 1 ;}else{right mid ;}}return list.get(left);}
}
