在链表中添加搜索功能。

huangapple go评论106阅读模式
英文:

add search function in linkedlist

问题

  1. def search(self, text, cur=None):
  2. if not cur:
  3. cur = self.head
  4. if cur.value == text or text in cur.value:
  5. return True
  6. if cur.next and cur.next != self.head:
  7. return self.search(text, cur.next)
  8. 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.

  1. class Node:
  2. def __init__(self, value):
  3. self.value = value
  4. self.next = None
  5. class LinkedList:
  6. def __init__(self, head = None):
  7. self.head = head
  8. def append(self, new_node):
  9. curr = self.head
  10. if curr:
  11. while curr.next:
  12. curr = curr.next
  13. curr.next = new_node
  14. else:
  15. self.head = new_node
  16. def search(self, text, cur):
  17. if cur.value == text:
  18. return True
  19. while cur.next != self.head and cur.next != None:
  20. if cur.next:
  21. cur = cur.next
  22. if cur.value == text:
  23. return True
  24. 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 the head 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 the while 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:

  1. def startswith(self, text, cur):
  2. while cur and text.startswith(cur.value):
  3. text = text[len(cur.value):]
  4. if not text:
  5. return True
  6. cur = cur.next
  7. return False
  8. def search(self, text, cur):
  9. if not text: # Boundary case
  10. return True # Or False, whatever you expect to happen
  11. while cur and not self.startswith(text, cur):
  12. cur = cur.next
  13. return cur is not None

Example code to run your example scenario:

  1. lst = LinkedList()
  2. for word in "I am a python developer".split(" "):
  3. lst.append(Node(word))
  4. 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 the head 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 the while 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:

  1. def startswith(self, text, cur):
  2. while cur and text.startswith(cur.value):
  3. text = text[len(cur.value):]
  4. if not text:
  5. return True
  6. cur = cur.next
  7. return False
  8. def search(self, text, cur):
  9. if not text: # Boundary case
  10. return True # Or False, whatever you expect to happen
  11. while cur and not self.startswith(text, cur):
  12. cur = cur.next
  13. return cur is not None

Example code to run your example scenario:

  1. lst = LinkedList()
  2. for word in "I am a python developer".split(" "):
  3. lst.append(Node(word))
  4. print(lst.search("apython", lst.head)) # True

huangapple
  • 本文由 发表于 2023年5月6日 19:33:09
  • 转载请务必保留本文链接:https://go.coder-hub.com/76188628.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定