0014_longest_common_prefix.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Longest Common Prefix - LeetCode 14</title>
    <link rel="stylesheet" href="styles.css">
    <script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
    <div class="container">
        <div class="problem-info">
            <h1><span class="problem-number">#14</span> Longest Common Prefix</h1>
            <p>Find the longest common prefix string amongst an array of strings.</p>
            <div class="problem-meta">
                <span class="meta-tag">String</span>
                <span class="meta-tag">Easy</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0014_longest_common_prefix/0014_longest_common_prefix.py</code>
            </div>

        </div>

        <div class="explanation-panel">
            <h4>🧠 How It Works (Layman's Terms)</h4>
            <p>Finding a common prefix by <strong>shrinking a candidate</strong>:</p>
            <ul>
                <li><strong>Start:</strong> Take the first string as the candidate prefix</li>
                <li><strong>Compare:</strong> Check each following string against the candidate</li>
                <li><strong>Shrink:</strong> Drop the last character until the string starts with it</li>
                <li><strong>Answer:</strong> Whatever survives all strings</li>
            </ul>
        </div>


        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>
            <div class="controls">
                <button id="stepBtn">Step</button>
                <button id="autoBtn">Auto Run</button>
                <button id="resetBtn">Reset</button>
            </div>
            <svg id="mainSvg" width="800" height="350"></svg>
            <div class="status-message" id="status">Click "Step" to find longest common prefix</div>
        </div>

        <div class="code-section">
            <h3>💻 Python Solution</h3>
            <div class="code-block">
                <pre>from typing import List

"""
LeetCode Longest Common Prefix

Problem from LeetCode: https://leetcode.com/problems/longest-common-prefix/

Description:
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
"""

class Solution:
    def longest_common_prefix(self, strs: List[str]) -&gt; str:
        """
        Find the longest common prefix string amongst an array of strings.
        
        Args:
            strs: Array of strings
            
        Returns:
            str: Longest common prefix, or empty string if no common prefix exists
        """
        if not strs:
            return ""
            
        # Start with the first string as the prefix
        prefix = strs[0]
        
        # Compare prefix with each string in the array
        for i in range(1, len(strs)):
            # Keep reducing the prefix until it's a prefix of the current string
            while strs[i].find(prefix) != 0:
                prefix = prefix[:-1]
                if not prefix:
                    return ""
                    
        return prefix
    
    def longest_common_prefix_vertical(self, strs: List[str]) -&gt; str:
        """
        Find the longest common prefix using vertical scanning approach.
        
        Args:
            strs: Array of strings
            
        Returns:
            str: Longest common prefix
        """
        if not strs:
            return ""
            
        for i in range(len(strs[0])):
            char = strs[0][i]
            # Compare the character at position i in all strings
            for j in range(1, len(strs)):
                # If we've reached the end of a string or characters don't match
                if i &gt;= len(strs[j]) or strs[j][i] != char:
                    return strs[0][:i]
                    
        # If we get here, the entire first string is a prefix
        return strs[0]
    
    def longest_common_prefix_divide_conquer(self, strs: List[str]) -&gt; str:
        """
        Find the longest common prefix using divide and conquer approach.
        
        Args:
            strs: Array of strings
            
        Returns:
            str: Longest common prefix
        """
        if not strs:
            return ""
            
        def common_prefix(left: str, right: str) -&gt; str:
            """Find common prefix of two strings."""
            min_len = min(len(left), len(right))
            for i in range(min_len):
                if left[i] != right[i]:
                    return left[:i]
            return left[:min_len]
            
        def divide_and_conquer(start: int, end: int) -&gt; str:
            """Apply divide and conquer to find common prefix."""
            if start == end:
                return strs[start]
                
            mid = (start + end) // 2
            left_prefix = divide_and_conquer(start, mid)
            right_prefix = divide_and_conquer(mid + 1, end)
            
            return common_prefix(left_prefix, right_prefix)
            
        return divide_and_conquer(0, len(strs) - 1)


if __name__ == '__main__':
    # Example usage based on LeetCode sample
    solution = Solution()
    
    # Example 1
    strs1 = ["flower", "flow", "flight"]
    result1 = solution.longest_common_prefix(strs1)
    print(f"Example 1: {strs1} -&gt; '{result1}'")  # Expected output: "fl"
    
    # Example 2
    strs2 = ["dog", "racecar", "car"]
    result2 = solution.longest_common_prefix(strs2)
    print(f"Example 2: {strs2} -&gt; '{result2}'")  # Expected output: ""
    
    # Additional example
    strs3 = ["hello", "heaven", "heavy"]
    result3 = solution.longest_common_prefix(strs3)
    print(f"Example 3: {strs3} -&gt; '{result3}'")  # Expected output: "he"
    
    # Compare approaches
    print("\nComparing different approaches:")
    print(f"Horizontal scanning: '{solution.longest_common_prefix(strs1)}'")
    print(f"Vertical scanning: '{solution.longest_common_prefix_vertical(strs1)}'")
    print(f"Divide and conquer: '{solution.longest_common_prefix_divide_conquer(strs1)}'")
</pre>
            </div>
        </div>
    </div>

    <script>
        const strs = ["flower", "flow", "flight"];
        const width = 800, height = 350;
        const svg = d3.select("#mainSvg");

        let charIndex = 0;
        let strIndex = 0;
        let prefix = "";
        let phase = 'comparing';
        let mismatch = false;
        
        let autoTimer = null;
        let autoRunning = false;

        function draw() {
            svg.selectAll("*").remove();

            const cellWidth = 45, cellHeight = 50;
            const startX = 120, startY = 70;

            // Title
            svg.append("text")
                .attr("x", width / 2).attr("y", 30)
                .attr("text-anchor", "middle")
                .attr("font-weight", "bold")
                .text(`Finding Longest Common Prefix in [${strs.map(s => `"${s}"`).join(", ")}]`);

            // Draw strings
            strs.forEach((str, sIdx) => {
                svg.append("text")
                    .attr("x", 30).attr("y", startY + sIdx * cellHeight + 30)
                    .attr("font-size", "14px")
                    .attr("fill", "#666")
                    .text(`strs[${sIdx}]:`);

                for (let cIdx = 0; cIdx < str.length; cIdx++) {
                    const x = startX + cIdx * cellWidth;
                    const y = startY + sIdx * cellHeight;
                    
                    let fill = "#f8fafc", stroke = "#94a3b8";
                    
                    if (cIdx < charIndex) {
                        fill = "#d1fae5"; stroke = "#10b981";
                    } else if (cIdx === charIndex) {
                        if (sIdx === strIndex) {
                            fill = "#fef3c7"; stroke = "#f59e0b";
                        } else if (sIdx < strIndex) {
                            fill = "#d1fae5"; stroke = "#10b981";
                        }
                        if (mismatch && sIdx === strIndex) {
                            fill = "#fee2e2"; stroke = "#ef4444";
                        }
                    }

                    svg.append("rect")
                        .attr("x", x).attr("y", y)
                        .attr("width", cellWidth - 5).attr("height", cellHeight - 5)
                        .attr("rx", 6)
                        .attr("fill", fill).attr("stroke", stroke)
                        .attr("stroke-width", cIdx === charIndex && sIdx === strIndex ? 3 : 2);

                    svg.append("text")
                        .attr("x", x + (cellWidth - 5) / 2)
                        .attr("y", y + (cellHeight - 5) / 2 + 6)
                        .attr("text-anchor", "middle")
                        .attr("font-size", "20px")
                        .attr("font-weight", "bold")
                        .text(str[cIdx]);
                }
            });

            // Column indicator
            if (charIndex < strs[0].length && !mismatch) {
                svg.append("text")
                    .attr("x", startX + charIndex * cellWidth + (cellWidth - 5) / 2)
                    .attr("y", startY - 15)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "12px")
                    .attr("fill", "#f59e0b")
                    .text(`▼ Column ${charIndex}`);
            }

            // Current prefix
            const prefixY = startY + strs.length * cellHeight + 30;
            
            svg.append("rect")
                .attr("x", 120).attr("y", prefixY)
                .attr("width", 300).attr("height", 50)
                .attr("rx", 10)
                .attr("fill", "#e8f5e9").attr("stroke", "#4caf50");

            svg.append("text")
                .attr("x", 270).attr("y", prefixY + 20)
                .attr("text-anchor", "middle")
                .attr("font-size", "12px")
                .text("Current Prefix:");

            svg.append("text")
                .attr("x", 270).attr("y", prefixY + 40)
                .attr("text-anchor", "middle")
                .attr("font-size", "20px")
                .attr("font-weight", "bold")
                .attr("fill", "#2e7d32")
                .text(prefix ? `"${prefix}"` : '""');

            // Final result
            if (phase === 'done') {
                svg.append("rect")
                    .attr("x", 450).attr("y", prefixY)
                    .attr("width", 250).attr("height", 50)
                    .attr("rx", 10)
                    .attr("fill", "#d1fae5").attr("stroke", "#10b981")
                    .attr("stroke-width", 2);

                svg.append("text")
                    .attr("x", 575).attr("y", prefixY + 32)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "18px")
                    .attr("font-weight", "bold")
                    .attr("fill", "#10b981")
                    .text(`Result: "${prefix}"`);
            }

            // Legend
            const legendY = 290;
            const legend = [
                { color: "#d1fae5", label: "Matched" },
                { color: "#fef3c7", label: "Comparing" },
                { color: "#fee2e2", label: "Mismatch" }
            ];

            legend.forEach((item, i) => {
                svg.append("rect")
                    .attr("x", 500 + i * 100).attr("y", legendY)
                    .attr("width", 15).attr("height", 15)
                    .attr("fill", item.color)
                    .attr("stroke", "#999");

                svg.append("text")
                    .attr("x", 520 + i * 100).attr("y", legendY + 12)
                    .attr("font-size", "11px")
                    .text(item.label);
            });
        }

        function step() {
            if (phase === 'done') return false;

            // Check if we've gone through all characters
            if (charIndex >= strs[0].length) {
                phase = 'done';
                document.getElementById("status").textContent = 
                    `Done! Longest common prefix: "${prefix}"`;
                draw();
                return false;
            }

            const targetChar = strs[0][charIndex];

            if (strIndex === 0) {
                document.getElementById("status").textContent = 
                    `Checking column ${charIndex}: comparing '${targetChar}'`;
                strIndex = 1;
            } else {
                // Check if current string has this character
                if (charIndex >= strs[strIndex].length || strs[strIndex][charIndex] !== targetChar) {
                    mismatch = true;
                    phase = 'done';
                    document.getElementById("status").textContent = 
                        charIndex >= strs[strIndex].length 
                            ? `String "${strs[strIndex]}" is too short. Done!`
                            : `Mismatch: '${strs[strIndex][charIndex]}' ≠ '${targetChar}'. Done!`;
                    draw();
                    return false;
                }

                document.getElementById("status").textContent = 
                    `'${strs[strIndex][charIndex]}' matches '${targetChar}'`;

                strIndex++;

                // All strings matched at this position
                if (strIndex >= strs.length) {
                    prefix += targetChar;
                    charIndex++;
                    strIndex = 0;
                    document.getElementById("status").textContent = 
                        `All matched! Prefix is now "${prefix}"`;
                }
            }

            draw();
            return phase !== 'done';
        }

        function reset() {
            charIndex = 0;
            strIndex = 0;
            prefix = "";
            phase = 'comparing';
            mismatch = false;
            if (autoTimer) clearInterval(autoTimer);
            autoRunning = false;
            document.getElementById("autoBtn").textContent = "Auto Run";
            document.getElementById("status").textContent = 'Click "Step" to find longest common prefix';
            draw();
        }

        function autoRun() {
            if (autoRunning) {
                clearInterval(autoTimer);
                autoRunning = false;
                document.getElementById("autoBtn").textContent = "Auto Run";
            } else {
                autoRunning = true;
                document.getElementById("autoBtn").textContent = "Pause";
                autoTimer = setInterval(() => {
                    if (!step()) {
                        clearInterval(autoTimer);
                        autoRunning = false;
                        document.getElementById("autoBtn").textContent = "Auto Run";
                    }
                }, 600);
            }
        }

        document.getElementById("stepBtn").addEventListener("click", step);
        document.getElementById("autoBtn").addEventListener("click", autoRun);
        document.getElementById("resetBtn").addEventListener("click", reset);

        reset();
    </script>
</body>
</html>