在链表中添加搜索功能。

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

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 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:

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 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:

    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

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:

确定