Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: TheAlgorithms/Python
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: master
Choose a base ref
...
head repository: furthermares/Python
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: master
Choose a head ref
Checking mergeability… Don’t worry, you can still create the pull request.
  • 3 commits
  • 1 file changed
  • 1 contributor

Commits on Jul 16, 2023

  1. Fix insertion fail in ["*X", "*XX"] cases

    Consider a word, and a copy of that word, but with the last letter repeating twice. (e.g., ["ABC", "ABCC"])
    When adding the second word's last letter, it only compares the previous word's prefix—the last letter of the word already in the Radix Tree: 'C'—and the letter to be added—the last letter of the word we're currently adding: 'C'. So it wrongly passes the "Case 1" check, marks the current node as a leaf node when it already was, then returns when there's still one more letter to add.
    The issue arises because `prefix` includes the letter of the node itself. (e.g., `nodes: {'C' : RadixNode()}, is_leaf: True, prefix: 'C'`) It can be easily fixed by simply adding the `is_leaf` check, asking if there are more letters to be added.
    
    - Test Case: `"A AA AAA AAAA"`
      - Fixed correct output:
      ```
      Words: ['A', 'AA', 'AAA', 'AAAA']
      Tree:
      - A   (leaf)
      -- A   (leaf)
      --- A   (leaf)
      ---- A   (leaf)
      ```
      - Current incorrect output:
      ```
      Words: ['A', 'AA', 'AAA', 'AAAA']
      Tree:
      - A   (leaf)
      -- AA   (leaf)
      --- A   (leaf)
      ```
    
    *N.B.* This passed test cases for [Croatian Open Competition in Informatics 2012/2013 Contest #3 Task 5 HERKABE](https://hsin.hr/coci/archive/2012_2013/)
    furthermares authored Jul 16, 2023
    Configuration menu
    Copy the full SHA
    4f29d20 View commit details
    Browse the repository at this point in the history

Commits on Jul 24, 2023

  1. Configuration menu
    Copy the full SHA
    a5b9868 View commit details
    Browse the repository at this point in the history
  2. Configuration menu
    Copy the full SHA
    d918fcb View commit details
    Browse the repository at this point in the history
Loading