实现 trie 数据结构
trie数据结构的strider讲解
class node{
node [] node = new node[26];
boolean flag;
public node(){
}
public boolean containskey(char c){
return node[c-'a']!=null;
}
public void put(char c, node n){
node[c-'a'] = n;
}
public node get(char c){
return node[c-'a'];
}
public void setflag() {
this.flag = true;
}
public boolean getflag(){
return this.flag;
}
}
class trie {
node root;
public trie() {
root = new node();
}
//will take tc : o(len) of the word
public void insert(string word) {
node node = root;
for(int i =0;i<word.length();i++){
if(!node.containskey(word.charat(i))){
node.put(word.charat(i),new node());
}
node = node.get(word.charat(i));
}
node.setflag();
}
//will take tc : o(len) of the word
public boolean search(string word) {
node node = root;
for(int i =0;i<word.length();i++){
if(!node.containskey(word.charat(i))){
return false;
}
node = node.get(word.charat(i));
}
return node.getflag();
}
//will take tc : o(len) of the prefix
public boolean startswith(string prefix) {
node node = root;
for(int i =0;i<pre class="brush:php;toolbar:false;"fix.length();i++){
if(!node.containskey(prefix.charat(i))){
return false;
}
node = node.get(prefix.charat(i));
}
return true;
}
}
/**
* your trie object will be instantiated and called as such:
* trie obj = new trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startswith(prefix);
*/
trie数据结构二
奋斗者的解释，以便更好理解
import java.util.* ;
import java.io.*;
class node {
node node[] = new node[26];
int endwith = 0;// will keep track of no. of words ending with this word
int countprefix=0;// will keep track of no. of words starting with this word
public node(){
}
public boolean containskey(char c){
return node[c-'a']!=null;
}
public void put(char c, node n){
node[c-'a'] = n;
}
public node get(char c){
return node[c-'a'];
}
public void incrementcountprefix() {
++this.countprefix;
}
public void decrementcountprefix(){
--this.countprefix;
}
public void incrementendwith(){
++this.endwith;
}
public void deleteendwith(){
--this.endwith;
}
public int getcountprefix(){
return this.countprefix;
}
public int getendwith(){
return this.endwith;
}
}
public class trie {
node root;
public trie() {
// write your code here.
root = new node();
}
public void insert(string word) {
node node = root;
for(int i =0;i<word.length();i++){
if(!node.containskey(word.charat(i))){
node.put(word.charat(i),new node());
}
node = node.get(word.charat(i));
node.incrementcountprefix();
}
node.incrementendwith();
}
public int countwordsequalto(string word) {
// write your code here.
node node = root;
for(int i=0;i<word.length();i++){
if(node.containskey(word.charat(i))){
node = node.get(word.charat(i));
}
else return 0;
}
return node.getendwith();//this will tell how many strings are
//ending with given word
}
public int countwordsstartingwith(string word) {
node node = root;
for(int i=0;i<word.length();i++){
if(node.containskey(word.charat(i))){
node = node.get(word.charat(i));
}
else return 0;
}
return node.getcountprefix(); // it will tell how many strings are starting
//with given word;
}
public void erase(string word) {
node node = root;
for(int i =0;i<word.length();i++){
if(node.containskey(word.charat(i))){
node = node.get(word.charat(i));
node.decrementcountprefix();
}
else return;
}
node.deleteendwith();
}
}
完整字符串
// tc : o(n*l)
import java.util.* ;
import java.io.*;
class node{
node[] node = new node[26];
boolean flag;
public node(){}
public void put(char c , node n){
node[c-'a'] = n;
}
public boolean containskey(char c){
return node[c-'a']!=null;
}
public node get(char c){
return node[c-'a'];
}
public void setend(){
this.flag = true;
}
public boolean isend(){
return this.flag;
}
}
class trie{
node root;
public trie(){
root = new node();
}
public boolean checkifprefixpresent(string s){
node node = root;
boolean flag= true;
for(int i = 0;i<s.length();i++){
char c = s.charat(i);
if(!node.containskey(c)){
return false;
}
node = node.get(c);
flag = flag && node.isend(); // this will check if the substring is also a string from the list of strings
//if(flag == false) return false; // this line will also work here because if any substring is not present as a string in the trie , then
// this string s won't be a complete string, and we can return false here only
}
return flag;
}
public void insert(string s){
node node = root;
for(int i =0;i<s.length();i++){
char c = s.charat(i);
if(!node.containskey(c)){
node.put(c, new node());
}
node = node.get(c);
}
node.setend(); // setting end of the string as this is the
//end of the current string s
}
}
class solution {
static node root;
public static string completestring(int n, string[] a) {
trie trie = new trie();
//storing all the string in the trie data structure
for(string s : a) trie.insert(s);
//finding out the comeplete string among all the list of strings
string completestring = "";
for(string s : a){
if(trie.checkifprefixpresent(s)){
if(completestring.length() < s.length()){
completestring = s;
}
//lexographical selection : a.compareto(b) =-1 if a < b lexographically
else if(completestring.length() == s.length() && s.compareto(completestring) < 0){
completestring = s;
}
}
}
return completestring.equals("") ? "none":completestring;
}
}
计算不同子串的个数
tc：在
中插入不同的唯一子字符串的 o(n^2)
trie数据结构
import java.util.ArrayList;
public class Solution
{
Node root;
static int count;
public Solution(){
root = new Node();
}
public static int countDistinctSubstrings(String s)
{
count = 0;
// Write your code here.
Solution sol = new Solution();
for(int i =0;i< s.length();i++){
String str = "";
for (int j =i;j< s.length();j++){
str = str+s.charAt(j);
sol.insert(str);
}
}
return count+1;
}
public void insert(String s){
Node node = root;
for(int i =0;i< s.length();i++){
if(!node.containsKey(s.charAt(i))){
node.put(s.charAt(i),new Node());
count++;
}
node = node.get(s.charAt(i));
}
node.setFlag();
}
}
class Node {
Node node[] = new Node[26];
boolean flag;
public Node(){
}
public boolean containsKey(char c){
return node[c-'a']!=null;
}
public Node get(char c){
return node[c-'a'];
}
public void put(char c, Node n){
node[c-'a'] = n;
}
public void setFlag(){
this.flag = true;
}
public boolean getFlag(){
return this.flag;
}
}
