现在牛牛想知道给出的字符串中有多少个原根。
(相同字符串互为前缀)
3,["a","ab","ba"]
2
"a"是原根因为"a"是"ab"的前缀,所以"ab"不是原根"ba"是原根
第一个参数n代表字符串个数
第二个参数vector s包含n个元素代表给出的字符串。
#include <unordered_set> class Solution { public: /** * 原根 * @param n int整型 * @param s string字符串vector * @return int整型 */ int solve(int n, vector<string>& s) { vector<vector<int>> T(1, vector<int>(26, 0)); unordered_set<int> S; for(auto &w: s){ int i=0, j=0; while(j<w.length() && T[i][w[j]-'a']) i = T[i][w[j++]-'a']; unordered_set<int>::iterator it = S.find(i); if(it != S.end()) S.erase(it); while(j < w.length()){ T[i][w[j++]-'a'] = T.size(); i = T.size(); T.push_back(vector<int>(26, 0)); if(j == w.length()) S.insert(i); } } return S.size(); } };
import java.util.*; import java.util.Comparator; import java.util.stream.Stream; import java.util.stream.Collectors; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @param s string字符串一维数组 * @return int整型 */ public int solve (int n, String[] s) { HashMap<String, Integer> map = new HashMap<>(); for(String str : s) { if(map.containsKey(str)) { map.remove(str); map.put(str, -1); }else { map.put(str, 1); } } int index = 0; for(HashMap.Entry entry: map.entrySet()) { if((Integer)entry.getValue() == 1) { entry.setValue(index++); } } String[] arr = new String[index]; for(HashMap.Entry entry : map.entrySet()) { if((Integer)entry.getValue() > -1) arr[(Integer)entry.getValue()] = (String)entry.getKey(); } /* 编译提示不通过,但运行正常*/ List<String> list = Arrays.asList(arr); Object[] array = list.stream().sorted(Comparator.comparing(String::length) .thenComparing(Comparator.naturalOrder())).toArray(); int count = 0; TrieNode root = new TrieNode(); for(Object obj : array) { if(root.insert((String)obj)) { count++; } } return count; } } class TrieNode { private final int CHAR_COUNT = 26; private TrieNode[] child; private boolean end; TrieNode() { this.child = new TrieNode[CHAR_COUNT]; this.end = false; } public int getIndexFromChar(char c) { return (c - 'a'); } public boolean insert(String str) { TrieNode cur = this; for(int i = 0; i < str.length(); i++) { int index = this.getIndexFromChar(str.charAt(i)); if(cur.child[index] != null && cur.child[index].end == true) return false; if(cur.child[index] == null) { cur.child[index] = new TrieNode(); cur = cur.child[index]; } } cur.end = true; return true; } }
#include <numeric> class Solution { public: int solve(int n, vector<string>& s) { vector<vector<int>> trie(1, vector<int>(26)); vector<int> a(1); for (auto si: s) { int i = 0, j = 0; while (j < si.length() && trie[i][si[j] - 'a']) i = trie[i][si[j++] - 'a']; a[i] = 0; while (j < si.length()) { i = trie[i][si[j++] - 'a'] = trie.size(); trie.push_back(vector<int>(26)); a.push_back(j == si.length()); } } return accumulate(a.begin(), a.end(), 0); } };
class Tree { public: bool isend = false; Tree* next[26]; }; bool myStrCmp(string a, string b) { //两个字符串比较长度,如果长度相同,就按照字母表排序。 if (a.size() == b.size()) return a < b; return a.size() < b.size(); } class Solution { public: int solve(int n,vector<string>s){ int res = 0; Tree* head = new Tree();//字典树的头 sort(s.begin(), s.end(),myStrCmp);//将字符串从短到长排序 for (int i = 0; i < s.size(); i++) { bool flag = false; while (i + 1 < n&&s[i].size() == s[i + 1].size()) { //比较两个长度相同的字符串是不是内容也相同 if (s[i] == s[i + 1]) {//如果两者相同,再比较下下个 flag = true; i++; } else { break; } } if (flag) continue; if (!find(head, s[i])) {//没有在字典树找到该单词的原根 res++; } bulid(head, s[i]);//将该单词加入字典树 } return res; } void bulid(Tree* head, string word) { //将单词插入字典树 for (int i = 0; i < word.size(); i++) { if (head->next[word[i] - 'a']!=NULL) { //如果该字母已经存在,则下移一级 head = head->next[word[i] - 'a']; } else { //该字母不存在,插入到这个树下面 for (int j = i; j < word.size(); j++) { Tree *node = new Tree(); head->next[word[j] - 'a'] = node; head = head->next[word[j] - 'a']; } head->isend = true; break; } } } bool find(Tree* head, string word) { //查找现在的字典树里面是否有word单词的原根 //如果有,则返回true int i = 0; for (; i < word.size(); i++) { if (head->next[word[i] - 'a'] != NULL ) { if(head->next[word[i] - 'a']->isend)//已经到原根的末尾 return true; head = head->next[word[i] - 'a']; } else { return false; } } return false; } };