英文:
add search function in linkedlist
问题
def search(self, text, cur=None):
if not cur:
cur = self.head
if cur.value == text or text in cur.value:
return True
if cur.next and cur.next != self.head:
return self.search(text, cur.next)
return False
英文:
I plan to add a search function in python linkedlist. It aims to search a string whether in the linkedlist or not (Each node of the linkedlist has a word). For example, if the linkedlist is : I -> am -> a -> python -> developer. If I search the text 'python', it will return True, if I search the text 'apython', it will return True, but if I search 'java' or 'ajava' it will return false. I write my codes as below, but search function cannot work. I am not sure should I add recursive function to solve the issue.
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self, head = None):
self.head = head
def append(self, new_node):
curr = self.head
if curr:
while curr.next:
curr = curr.next
curr.next = new_node
else:
self.head = new_node
def search(self, text, cur):
if cur.value == text:
return True
while cur.next != self.head and cur.next != None:
if cur.next:
cur = cur.next
if cur.value == text:
return True
return False
答案1
得分: 1
Your code is only testing cases where the text matches completely with a single node value.
Some other remarks:
-
cur.next != self.head
is never going to be true. By definition thehead
node is the first node of the list, so it will never be the successor after a given node. -
The
if cur.next
is overkill, because that condition is always going to be true - it was the reason why thewhile
loop didn't exit yet. -
if cur.value == text
appears twice in your code. This should not be necessary. Apply DRY.
But as stated, the main issue is that there is no code that tries to match a node with part of the given text.
One of the ways to tackle this is to write two functions: one to check if the given node is the start of a series of nodes that together match the given text. Another function can call the first function on each node of the list. If any of those leads to success, then the search is successful.
Here is the code for that:
def startswith(self, text, cur):
while cur and text.startswith(cur.value):
text = text[len(cur.value):]
if not text:
return True
cur = cur.next
return False
def search(self, text, cur):
if not text: # Boundary case
return True # Or False, whatever you expect to happen
while cur and not self.startswith(text, cur):
cur = cur.next
return cur is not None
Example code to run your example scenario:
lst = LinkedList()
for word in "I am a python developer".split(" "):
lst.append(Node(word))
print(lst.search("apython", lst.head)) # True
英文:
Your code is only testing cases where the text matches completely with a single node value.
Some other remarks:
-
cur.next != self.head
is never going to be true. By definition thehead
node is the first node of the list, so it will never be the successor after a given node. -
The
if cur.next
is overkill, because that condition is always going to be true - it was the reason why thewhile
loop didn't exit yet. -
if cur.value == text
appears twice in your code. This should not be necessary. Apply DRY.
But as stated, the main issue is that there is no code that tries to match a node with part of the given text.
One of the ways to tackle this, is to write two functions: one to check if the given node is the start of a series of nodes that together match the given text. Another function can call the first function on each node of the list. If any of those leads to success, then the search is successful.
Here is the code for that:
def startswith(self, text, cur):
while cur and text.startswith(cur.value):
text = text[len(cur.value):]
if not text:
return True
cur = cur.next
return False
def search(self, text, cur):
if not text: # Boundary case
return True # Or False, whatever you expect to happen
while cur and not self.startswith(text, cur):
cur = cur.next
return cur is not None
Example code to run your example scenario:
lst = LinkedList()
for word in "I am a python developer".split(" "):
lst.append(Node(word))
print(lst.search("apython", lst.head)) # True
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论