Attribute error in Trie implementation

help
, ,
1

I was doing this this question on leetcode and got AC in C++ . code

But same code in python3 this gives me attribute error. Probably , error is in line
if node.c[ord(s[idx])-ord(‘a’)] == None:
node.c[ord(s[idx])-ord(‘a’)] == self.Tr()

in insertu function where new node is not being assigned .Can anyone help me rectify it !
Thanks in advance :wink:

2

The attached link of your .Py and C++ code shows page not found.

3

Can you paste your code in between a pair of 3 backticks(`) or provide a Working (I mean, globally accessible) link to your code?

4

Problem is from leetcode u need to login however for simplicity I’m pasting it right here :

Here is the python version of code :

class Trie:
class Tr:
def init(self):
self.c = [None for _ in range(52)]
self.eof = False

def __init__(self):
    self.T = self.Tr()

def newnode(self):
    tmp = self.Tr()
    return tmp

def insertu(self,s,idx,node) -> None:
    if idx==len(s):
        node.eof = True
        return
    if node.c[ord(s[idx])-ord('a')] == None:
        node.c[ord(s[idx])-ord('a')] == self.Tr()

    self.insertu(s,idx+1,node.c[ord(s[idx])-ord('a')])

def searchu(self,s:str,idx:int,node:Tr) -> bool:
    if idx == len(s):
        return node.eof
    if (not node.c[ord(s[idx])-ord('a')]):
        return False
    return self.searchu(s,idx+1,node.c[ord(s[idx])-ord('a')])

def stu(self,s:str,idx:int,node:Tr) -> bool:
    if id==len(s):
        return True
    if not node.c[ord(s[idx])-ord('a')]:
        return False
    return self.stu(s,id+1,node.c[ord(idx)--ord('a')])


def insert(self, word: str) -> None:
    self.insertu(word,0,self.T)
    return

def search(self, word: str) -> bool:
    return self.searchu(word,0,self.T)

def startsWith(self, prefix: str) -> bool:
    return stu(prefix,0,self.T)

Gives error :
Runtime Error Message: AttributeError: ‘NoneType’ object has no attribute ‘c’
if node.c[ord(s[idx])-ord(‘a’)] == None:
Line 19 in insertu (Solution.py)
self.insertu(s,idx+1,node.c[ord(s[idx])-ord(‘a’)])
Line 22 in insertu (Solution.py)
self.insertu(word,0,self.T)
Line 40 in insert (Solution.py)
result = obj.insert(
Line 59 in helper_select_method (Solution.py)
ret.append(DriverSolution().helper_select_method(method, params[index], obj))
Line 111 in _driver (Solution.py)
_driver()
Line 120 in (Solution.py)

Meanwhile accepted CPP code :
class Trie {
public:
/** Initialize your data structure here. /
class tr{
public:
tr c[52];
bool eof;
tr() {
eof = 0;
for (int i=0;i<52;++i) c[i]=NULL;
}
};

tr* T;


Trie() {
    T = new tr();
}

void insertU(string& s,int idx,tr*&node){
    if (idx==s.length()){
        node->eof = 1;
        return;
    }
    if (node->c[s[idx]-'a']==NULL){
        node->c[s[idx]-'a']= new tr();
    }
    
    insertU(s,idx+1,node->c[s[idx]-'a']);
}

/** Inserts a word into the trie. */
void insert(string word) {
    insertU(word,0,T);
}

bool searchU(string& s,int id,tr*& node){
    if (id==s.length()) return (node->eof);

    if (not node->c[s[id]-'a']) return 0;

    return searchU(s,id+1,node->c[s[id]-'a']);
}


/** Returns if the word is in the trie. */
bool search(string word) {
    return searchU(word,0,T);
}

bool stU(string& s,int id,tr*& node){
    if (id==s.length()) return 1;
    if (not node->c[s[id]-'a']) return 0;
    return stU(s,id+1,node->c[s[id]-'a']);
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
    if (stU(prefix,0,T)) return 1;
    else return 0;
}

};

/**

  • Your Trie object will be instantiated and called as such:
  • Trie* obj = new Trie();
  • obj->insert(word);
  • bool param_2 = obj->search(word);
  • bool param_3 = obj->startsWith(prefix);
    */
5

I resolved error myself.

Thanks for your time :wink: