X Tutup
The Wayback Machine - https://web.archive.org/web/20260216091509/https://github.com/TheAlgorithms/Python/pull/3958
Skip to content

Add greedy method for longest palindromic subsequence#3958

Closed
gideonshaked wants to merge 3 commits intoTheAlgorithms:masterfrom
gideonshaked:greedy-lps
Closed

Add greedy method for longest palindromic subsequence#3958
gideonshaked wants to merge 3 commits intoTheAlgorithms:masterfrom
gideonshaked:greedy-lps

Conversation

@gideonshaked
Copy link

@gideonshaked gideonshaked commented Nov 26, 2020

Describe your change:

Add a recursive backtracking programming solution to the longest palindromic subsequence problem.

  • Add an algorithm?
  • Fix a bug or typo in an existing algorithm?
  • Documentation change?

Checklist:

  • I have read CONTRIBUTING.md.
  • This pull request is all my own work -- I have not plagiarized.
  • I know that pull requests will not be merged if they fail the automated tests.
  • This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
  • All new Python files are placed inside an existing directory.
  • All filenames are in all lowercase characters with no spaces or dashes.
  • All functions and variable names follow Python naming conventions.
  • All function parameters and return values are annotated with Python type hints.
  • All functions have doctests that pass the automated testing.
  • All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
  • If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.

@ghost ghost added the awaiting reviews This PR is ready to be reviewed label Nov 26, 2020
@ghost
Copy link

ghost commented Nov 26, 2020 •
edited by dhruvmanila
Loading

Pull Request Report

@The-Kid-Gid Hello! I'm a bot made to check all the pull request Python files. First of all, I want to say thank you for your time and interest in this project and for opening a pull request.

I have detected errors in some of the Python files submitted in this pull request. Please read through the report and make the necessary changes. You can take a look at the relevant links provided after the report.

What are node paths? 🔽

The report contain headings and a checklist where the items are paths to the class/function/parameter where the error is present. Node paths are double colon :: separated names and can be any of the following format:

  • Class path: [file_name]::[class_name]
  • Function path: [file_name]::[function_name]
  • Function parameter path: [file_name]::[function_name]::[parameter_name]
  • Method path: [file_name]::[class_name]::[function_name]
  • Method parameter path: [file_name]::[class_name]::[function_name]::[parameter_name]

Following class/functions/parameters require descriptive names:

  • greedy_method/greedy_longest_palindromic_subsequence.py::longest_palindromic_subsequence::i
  • greedy_method/greedy_longest_palindromic_subsequence.py::longest_palindromic_subsequence::j
Relevant links 🔽

@ghost ghost added require descriptive names This PR needs descriptive function and/or variable names and removed awaiting reviews This PR is ready to be reviewed labels Nov 26, 2020
@ghost ghost mentioned this pull request Nov 26, 2020
Closed
14 tasks
@ghost ghost added awaiting reviews This PR is ready to be reviewed tests are failing Do not merge until tests pass and removed require descriptive names This PR needs descriptive function and/or variable names awaiting reviews This PR is ready to be reviewed labels Nov 26, 2020
@ghost ghost added awaiting reviews This PR is ready to be reviewed and removed tests are failing Do not merge until tests pass labels Nov 26, 2020
@ghost
Copy link

ghost commented Nov 26, 2020

@dhruvmanila check this
Also, I think it will end up with recursion error at some point with long strings

dhruvmanila
dhruvmanila reviewed Nov 26, 2020
View reviewed changes
greedy_method/greedy_longest_palindromic_subsequence.py
to occupy consecutive positions.

Explanation:
https://www.techiedelight.com/longest-palindromic-subsequence-using-dynamic-programming/
Copy link
Member

@dhruvmanila dhruvmanila Nov 26, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This code is a direct copy from the mentioned link.
@cclauss Please take a look at this.

Copy link

@ghost ghost Nov 26, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

true, only a few names are changed which was recommended by bot

@cclauss
Copy link
Member

cclauss commented Nov 26, 2020 •
edited
Loading

Closing. This is code copied from elsewhere and we are already planning to remove the greedy_method directory because it does not fit in with our other root directories. #3956

@cclauss cclauss closed this Nov 26, 2020
@gideonshaked
Copy link
Author

gideonshaked commented Nov 26, 2020

@cclauss @dhruvmanila @xcodz-dot thanks. I followed the explanation of the algorithm from the article and my code turned out very similar. I didn't mean to waste the time of the maintainers, and I understand your decision.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@dhruvmanila dhruvmanila dhruvmanila left review comments

+1 more reviewer
Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

awaiting reviews This PR is ready to be reviewed

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@gideonshaked @cclauss @dhruvmanila
X Tutup