Coding Challenges: Engage and Learn Through Problem Solving

03010

Coding Challenges: Engage and Learn Through Problem Solving

Coding challenges are a fantastic way to improve your programming skills, engage with a community, and learn new techniques. In this blog post, we’ll present a coding challenge, discuss various approaches to solve it, and invite readers to share their solutions in the comments. Let’s dive in!

Challenge: Find the Longest Palindromic Substring

Problem:
Given a string s, find the longest palindromic substring in s. A palindrome is a string that reads the same backward as forward.

Example: 

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Enter fullscreen mode Exit fullscreen mode

Constraints:

  • 1 <= s.length <= 1000
  • s consists of only digits and English letters.

Please share your Solutions with creative approaches using different programming languages.

Step-by-Step Guide to Solve the Challenge

Step 1: Understand the Problem

Before jumping into the code, make sure you understand the problem. A palindromic substring is a sequence of characters that reads the same backward as forward. Our goal is to find the longest such substring in the given string s.

Step 2: Plan Your Approach

There are several ways to solve this problem. We’ll discuss three approaches:

  1. Brute Force
  2. Expand Around Center
  3. Dynamic Programming

Step 3: Implement the Brute Force Approach

The brute force approach involves checking all possible substrings and determining if they are palindromes. This method is straightforward but not efficient for large strings. 

<span>def</span> <span>longest_palindrome_brute_force</span><span>(</span><span>s</span><span>):</span>
    <span>def</span> <span>is_palindrome</span><span>(</span><span>sub</span><span>):</span>
        <span>return</span> <span>sub</span> <span>==</span> <span>sub</span><span>[::</span><span>-</span><span>1</span><span>]</span>
    <span>n</span> <span>=</span> <span>len</span><span>(</span><span>s</span><span>)</span>
    <span>longest</span> <span>=</span> <span>""</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
        <span>for</span> <span>j</span> <span>in</span> <span>range</span><span>(</span><span>i</span><span>,</span> <span>n</span><span>):</span>
            <span>if</span> <span>is_palindrome</span><span>(</span><span>s</span><span>[</span><span>i</span><span>:</span><span>j</span><span>+</span><span>1</span><span>])</span> <span>and</span> <span>len</span><span>(</span><span>s</span><span>[</span><span>i</span><span>:</span><span>j</span><span>+</span><span>1</span><span>])</span> <span>></span> <span>len</span><span>(</span><span>longest</span><span>):</span>
                <span>longest</span> <span>=</span> <span>s</span><span>[</span><span>i</span><span>:</span><span>j</span><span>+</span><span>1</span><span>]</span>
    <span>return</span> <span>longest</span>
<span>print</span><span>(</span><span>longest_palindrome_brute_force</span><span>(</span><span>"</span><span>babad</span><span>"</span><span>))</span>  <span># Output: "bab" or "aba" </span>
<span>def</span> <span>longest_palindrome_brute_force</span><span>(</span><span>s</span><span>):</span>
    <span>def</span> <span>is_palindrome</span><span>(</span><span>sub</span><span>):</span>
        <span>return</span> <span>sub</span> <span>==</span> <span>sub</span><span>[::</span><span>-</span><span>1</span><span>]</span>

    <span>n</span> <span>=</span> <span>len</span><span>(</span><span>s</span><span>)</span>
    <span>longest</span> <span>=</span> <span>""</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
        <span>for</span> <span>j</span> <span>in</span> <span>range</span><span>(</span><span>i</span><span>,</span> <span>n</span><span>):</span>
            <span>if</span> <span>is_palindrome</span><span>(</span><span>s</span><span>[</span><span>i</span><span>:</span><span>j</span><span>+</span><span>1</span><span>])</span> <span>and</span> <span>len</span><span>(</span><span>s</span><span>[</span><span>i</span><span>:</span><span>j</span><span>+</span><span>1</span><span>])</span> <span>></span> <span>len</span><span>(</span><span>longest</span><span>):</span>
                <span>longest</span> <span>=</span> <span>s</span><span>[</span><span>i</span><span>:</span><span>j</span><span>+</span><span>1</span><span>]</span>
    <span>return</span> <span>longest</span>


<span>print</span><span>(</span><span>longest_palindrome_brute_force</span><span>(</span><span>"</span><span>babad</span><span>"</span><span>))</span>  <span># Output: "bab" or "aba" </span>
def longest_palindrome_brute_force(s):
    def is_palindrome(sub):
        return sub == sub[::-1]

    n = len(s)
    longest = ""
    for i in range(n):
        for j in range(i, n):
            if is_palindrome(s[i:j+1]) and len(s[i:j+1]) > len(longest):
                longest = s[i:j+1]
    return longest


print(longest_palindrome_brute_force("babad"))  # Output: "bab" or "aba"

Enter fullscreen mode Exit fullscreen mode

Step 4: Implement the Expand Around Center Approach

This approach involves expanding around each character (and between characters) to find the longest palindrome. It’s more efficient than brute force. 

<span>def</span> <span>longest_palindrome_expand_center</span><span>(</span><span>s</span><span>):</span>
    <span>def</span> <span>expand_around_center</span><span>(</span><span>left</span><span>,</span> <span>right</span><span>):</span>
        <span>while</span> <span>left</span> <span>>=</span> <span>0</span> <span>and</span> <span>right</span> <span><</span> <span>len</span><span>(</span><span>s</span><span>)</span> <span>and</span> <span>s</span><span>[</span><span>left</span><span>]</span> <span>==</span> <span>s</span><span>[</span><span>right</span><span>]:</span>
            <span>left</span> <span>-=</span> <span>1</span>
            <span>right</span> <span>+=</span> <span>1</span>
        <span>return</span> <span>s</span><span>[</span><span>left</span><span>+</span><span>1</span><span>:</span><span>right</span><span>]</span>
    <span>longest</span> <span>=</span> <span>""</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>len</span><span>(</span><span>s</span><span>)):</span>
        <span># Odd length palindromes </span>        <span>odd_palindrome</span> <span>=</span> <span>expand_around_center</span><span>(</span><span>i</span><span>,</span> <span>i</span><span>)</span>
        <span>if</span> <span>len</span><span>(</span><span>odd_palindrome</span><span>)</span> <span>></span> <span>len</span><span>(</span><span>longest</span><span>):</span>
            <span>longest</span> <span>=</span> <span>odd_palindrome</span>
        <span># Even length palindromes </span>        <span>even_palindrome</span> <span>=</span> <span>expand_around_center</span><span>(</span><span>i</span><span>,</span> <span>i</span><span>+</span><span>1</span><span>)</span>
        <span>if</span> <span>len</span><span>(</span><span>even_palindrome</span><span>)</span> <span>></span> <span>len</span><span>(</span><span>longest</span><span>):</span>
            <span>longest</span> <span>=</span> <span>even_palindrome</span>
    <span>return</span> <span>longest</span>
<span>print</span><span>(</span><span>longest_palindrome_expand_center</span><span>(</span><span>"</span><span>babad</span><span>"</span><span>))</span>  <span># Output: "bab" or "aba" </span>
<span>def</span> <span>longest_palindrome_expand_center</span><span>(</span><span>s</span><span>):</span>
    <span>def</span> <span>expand_around_center</span><span>(</span><span>left</span><span>,</span> <span>right</span><span>):</span>
        <span>while</span> <span>left</span> <span>>=</span> <span>0</span> <span>and</span> <span>right</span> <span><</span> <span>len</span><span>(</span><span>s</span><span>)</span> <span>and</span> <span>s</span><span>[</span><span>left</span><span>]</span> <span>==</span> <span>s</span><span>[</span><span>right</span><span>]:</span>
            <span>left</span> <span>-=</span> <span>1</span>
            <span>right</span> <span>+=</span> <span>1</span>
        <span>return</span> <span>s</span><span>[</span><span>left</span><span>+</span><span>1</span><span>:</span><span>right</span><span>]</span>

    <span>longest</span> <span>=</span> <span>""</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>len</span><span>(</span><span>s</span><span>)):</span>
        <span># Odd length palindromes </span>        <span>odd_palindrome</span> <span>=</span> <span>expand_around_center</span><span>(</span><span>i</span><span>,</span> <span>i</span><span>)</span>
        <span>if</span> <span>len</span><span>(</span><span>odd_palindrome</span><span>)</span> <span>></span> <span>len</span><span>(</span><span>longest</span><span>):</span>
            <span>longest</span> <span>=</span> <span>odd_palindrome</span>
        <span># Even length palindromes </span>        <span>even_palindrome</span> <span>=</span> <span>expand_around_center</span><span>(</span><span>i</span><span>,</span> <span>i</span><span>+</span><span>1</span><span>)</span>
        <span>if</span> <span>len</span><span>(</span><span>even_palindrome</span><span>)</span> <span>></span> <span>len</span><span>(</span><span>longest</span><span>):</span>
            <span>longest</span> <span>=</span> <span>even_palindrome</span>
    <span>return</span> <span>longest</span>


<span>print</span><span>(</span><span>longest_palindrome_expand_center</span><span>(</span><span>"</span><span>babad</span><span>"</span><span>))</span>  <span># Output: "bab" or "aba" </span>
def longest_palindrome_expand_center(s):
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right]

    longest = ""
    for i in range(len(s)):
        # Odd length palindromes         odd_palindrome = expand_around_center(i, i)
        if len(odd_palindrome) > len(longest):
            longest = odd_palindrome
        # Even length palindromes         even_palindrome = expand_around_center(i, i+1)
        if len(even_palindrome) > len(longest):
            longest = even_palindrome
    return longest


print(longest_palindrome_expand_center("babad"))  # Output: "bab" or "aba"

Enter fullscreen mode Exit fullscreen mode

Step 5: Implement the Dynamic Programming Approach

The dynamic programming approach uses a table to store whether a substring is a palindrome, leading to an efficient solution. 

<span>def</span> <span>longest_palindrome_dp</span><span>(</span><span>s</span><span>):</span>
    <span>n</span> <span>=</span> <span>len</span><span>(</span><span>s</span><span>)</span>
    <span>if</span> <span>n</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>""</span>
    <span>dp</span> <span>=</span> <span>[[</span><span>False</span><span>]</span> <span>*</span> <span>n</span> <span>for</span> <span>_</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>)]</span>
    <span>start</span><span>,</span> <span>max_length</span> <span>=</span> <span>0</span><span>,</span> <span>1</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
        <span>dp</span><span>[</span><span>i</span><span>][</span><span>i</span><span>]</span> <span>=</span> <span>True</span>
    <span>for</span> <span>length</span> <span>in</span> <span>range</span><span>(</span><span>2</span><span>,</span> <span>n</span><span>+</span><span>1</span><span>):</span>
        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>-</span><span>length</span><span>+</span><span>1</span><span>):</span>
            <span>j</span> <span>=</span> <span>i</span> <span>+</span> <span>length</span> <span>-</span> <span>1</span>
            <span>if</span> <span>s</span><span>[</span><span>i</span><span>]</span> <span>==</span> <span>s</span><span>[</span><span>j</span><span>]:</span>
                <span>if</span> <span>length</span> <span>==</span> <span>2</span> <span>or</span> <span>dp</span><span>[</span><span>i</span><span>+</span><span>1</span><span>][</span><span>j</span><span>-</span><span>1</span><span>]:</span>
                    <span>dp</span><span>[</span><span>i</span><span>][</span><span>j</span><span>]</span> <span>=</span> <span>True</span>
                    <span>if</span> <span>length</span> <span>></span> <span>max_length</span><span>:</span>
                        <span>start</span> <span>=</span> <span>i</span>
                        <span>max_length</span> <span>=</span> <span>length</span>
    <span>return</span> <span>s</span><span>[</span><span>start</span><span>:</span><span>start</span><span>+</span><span>max_length</span><span>]</span>
<span>print</span><span>(</span><span>longest_palindrome_dp</span><span>(</span><span>"</span><span>babad</span><span>"</span><span>))</span>  <span># Output: "bab" or "aba" </span>
<span>def</span> <span>longest_palindrome_dp</span><span>(</span><span>s</span><span>):</span>
    <span>n</span> <span>=</span> <span>len</span><span>(</span><span>s</span><span>)</span>
    <span>if</span> <span>n</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>""</span>
    <span>dp</span> <span>=</span> <span>[[</span><span>False</span><span>]</span> <span>*</span> <span>n</span> <span>for</span> <span>_</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>)]</span>
    <span>start</span><span>,</span> <span>max_length</span> <span>=</span> <span>0</span><span>,</span> <span>1</span>

    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
        <span>dp</span><span>[</span><span>i</span><span>][</span><span>i</span><span>]</span> <span>=</span> <span>True</span>

    <span>for</span> <span>length</span> <span>in</span> <span>range</span><span>(</span><span>2</span><span>,</span> <span>n</span><span>+</span><span>1</span><span>):</span>
        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>-</span><span>length</span><span>+</span><span>1</span><span>):</span>
            <span>j</span> <span>=</span> <span>i</span> <span>+</span> <span>length</span> <span>-</span> <span>1</span>
            <span>if</span> <span>s</span><span>[</span><span>i</span><span>]</span> <span>==</span> <span>s</span><span>[</span><span>j</span><span>]:</span>
                <span>if</span> <span>length</span> <span>==</span> <span>2</span> <span>or</span> <span>dp</span><span>[</span><span>i</span><span>+</span><span>1</span><span>][</span><span>j</span><span>-</span><span>1</span><span>]:</span>
                    <span>dp</span><span>[</span><span>i</span><span>][</span><span>j</span><span>]</span> <span>=</span> <span>True</span>
                    <span>if</span> <span>length</span> <span>></span> <span>max_length</span><span>:</span>
                        <span>start</span> <span>=</span> <span>i</span>
                        <span>max_length</span> <span>=</span> <span>length</span>

    <span>return</span> <span>s</span><span>[</span><span>start</span><span>:</span><span>start</span><span>+</span><span>max_length</span><span>]</span>


<span>print</span><span>(</span><span>longest_palindrome_dp</span><span>(</span><span>"</span><span>babad</span><span>"</span><span>))</span>  <span># Output: "bab" or "aba" </span>
def longest_palindrome_dp(s):
    n = len(s)
    if n == 0:
        return ""
    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1

    for i in range(n):
        dp[i][i] = True

    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i+1][j-1]:
                    dp[i][j] = True
                    if length > max_length:
                        start = i
                        max_length = length

    return s[start:start+max_length]


print(longest_palindrome_dp("babad"))  # Output: "bab" or "aba"

Enter fullscreen mode Exit fullscreen mode

Try optimizing the algorithms.

原文链接：Coding Challenges: Engage and Learn Through Problem Solving

展开阅读全文
© 版权声明
文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
Python（EN）
# python# tutorial# algorithms# challenge
喜欢就支持一下吧
点赞10 分享
The future you will certainly thank yourself now desperately.
未来的你一定会感谢现在拼命的自己
评论 抢沙发

请登录后发表评论

    暂无评论内容

文章目录
kity的头像-拾光赋
文章目录
今日剩余 82.5%
本周剩余 54.6%
本月剩余 46.1%
本年剩余 70.9%
最近评论
杀人蜂的头像-拾光赋

杀人蜂3天前0

我很好奇这个网站能提供什么
Vito的头像-拾光赋

Vito6个月前2

你就是我心中的那首忐忑，总是让我惊心动魄
Jason.Meng的头像-拾光赋钻石会员

Jason.Meng徽章-人气大使-拾光赋6个月前2

总是会在人生的不同阶段反复爱上大佬的文章~
每日一言
The sacrifices you make today will pay dividends in the future.
今天的牺牲和努力未来都会有回报