Guide to High School Computer Science
  • 💻Introduction
    • windows & Python Development
    • macOS & Python Development
    • Visual Studio Code Settings
    • Set up Github
    • Author Page
  • 🧠Prerequisite Skills
    • Keyboard Typing
    • Files & Directories
    • Use of Command Line
    • Git & GitHub
    • Markdown
    • Starting Your Python Project
  • 🐍Python Programming
    • 🍎Python Basics
      • What is Python?
      • Procedural Programming & Programming Paradigms
      • String Formatting
      • Data Types
      • Input & Output to Console
      • Working with Numbers
      • Useful Built-in Functions
      • Math & Random Module
      • Boolean Data Object
      • Comparison, Logical, and Membership Operators
      • If Statements
      • Binary Decisions
      • Multiple Decisions
      • Nested Conditions
      • [EXTRA] Bitwise Operators
      • [EXTRA] Python Style Guide
    • ⏮️Iterations
      • Introduction to While Loops
      • Infinite Loop
      • Controlling Your While Loops
      • Introduction to For Loops
      • For Loops w/ Numeric Sequences
      • For Loops w/ Strings & Lists
      • Iterable Functions w/ For Loops
    • 📦Collections
      • Strings
        • String Basics
        • String Indexing
        • String Slicing
        • String Operators & Functions
        • Basic String Methods
        • String Methods Extended
        • String Methods Document
      • Tuples & Lists
        • Tuples
        • List Basics
        • List are Mutable
        • Adding Items to a List
        • Removing Items from a List
        • Search & Reverse a List
        • List Comprehension
        • List Methods Document
      • Sets
      • Dictionary
      • How to Store Multiple Data Items
    • 💡Defining Functions
      • Functions
      • print() vs return
      • Pre-determined Arguments
      • Nested Functions
      • Map & Filter
      • [Extra] Dynamic Arguments
    • 💾File I/O
      • How to Save Text to an External File
      • Reading CSV in Python
      • Reading JSON in Python
    • 🔨Basic Python Projects
      • Basic Calculator
        • Improving the calculator
        • Exercise Set 1
        • Exercise Set 2
        • 💎Streamlit Application #1
      • Basic Password Generator
        • Exercise Set 3
        • Exercises Related to Math
        • 💎Streamlit Application #2
      • A To-Do Task List
    • ⏳Introduction to Algorithmic Thinking
      • Big-O Notation
      • Basic Algorithms
        • Linear Search
        • Binary Search
        • Basic Sorting Algorithms
      • Recursion
      • Brute Force Algorithms
      • Greedy Algorithm
        • Time on Task (CCC 2013 J4)
        • Dijkstra’s Algorithm
      • Divide and Conquer
        • Merge Sort
      • Dynamic Programming
    • 🤯Object Oriented Programming
      • Class & Objects (Definitions)
      • OOP in Python
      • Encapsulation
      • Polymorphism
      • Inheritance & Overriding
      • Override Magic Methods
      • Case Study: 2D Vectors
      • Case Study: Deck of Cards
      • Exercise
      • Abstract Data Types
      • Case Study: Static 1D Array From Java
    • Competitive Programming
      • Is This Sum Possible?
        • Is the dataset sorted?
        • Searching for a value
        • Determine if the difference between an integer from the array and the target value exists
        • Sorting Algorithms
        • Using Two Pointers
      • Two Sum - LeetCode
        • Generate all possible pairs of values
        • Subtract each value from the target, see if the difference exists in the list
      • Longest Common Prefix - LeetCode
        • Compare all possible prefixes
        • Create the longest common prefix with the direct neighbour
      • Length of Last Word - LeetCode
        • Compare all possible prefixes
      • Where can I go from one point to another?
      • Sample Outline
    • IB Recipe Book
  • 💾Python & Databases
    • Intro to Databases & Data Modeling
      • Common Data Types in SQL
      • Introduction to ERDs
      • Primary Keys and Foreign Keys
      • Database Normalization
    • What is SQL?
      • Getting Started
      • SELECT Queries
        • Selection with Conditions
        • Selection with Fuzziness
        • Selection and Sorting in Order
        • Selection without Duplicates
        • Selection with Limited Number of Outputs
      • AGGREGATE Queries
        • Counting Rows
        • Sum, Average, Min/Max Queries
        • Working with Aggregate Queries
        • Power of using Groups
        • Exercise
      • Interacting with Multiple Table
      • Inserting Data
      • External Resource
  • ☕Java Essentials
    • Basics
      • Starting Java
      • Data & Variables
      • Handling User Inputs & Type Conversion
      • Arithmetic
      • IPO Model
      • Basic Built-in Methods
      • Exercise Questions
    • Conditionals
      • Boolean Operators
      • Compare Strings
      • If Statements
      • If Else Statements
      • Making Multiple Decisions
      • Using Switch
      • Flowchart Symbols
      • Exercise Questions
    • Iterations
      • While Loops
      • For Loop
      • Exercises
    • Java Type Casting
    • Strings
      • Common String Practices
      • String Formatting
      • Java Special Characters
    • Collection
      • Arrays
      • For Each Loop
      • ArrayList
      • Exercise Questions
    • Static Methods
      • (Aside) Clearing your Console
    • Randomness in Java
    • Delayed Output in Java
    • Java Output Formatting
    • Java Style Guide
  • 🛠️JavaScript Programming
    • Our Programming Editor & Workflow
      • Hello, world!
      • Commenting & Variables
      • Data in JavaScript
      • Operators
      • String Formatting
      • Getting User Input
    • JavaScript Exercise Set 1
    • Making Decisions
      • Comparing Values
      • Combining Boolean Comparisons
      • Creating Branches
    • JavaScript Exercise Set 2
    • While Loops
      • Infinite While Loop
      • While Loops and Numbers
      • While Loops and Flags
      • While loops w/ Strings
    • JavaScript Exercise Set 3
    • Subprograms & Functions
      • Creating a Function in JavaScript
      • Function with Input and Assignable Output
    • JavaScript Exercise Set 4
  • 💾Topics in CS
    • Computer Environments & Systems
      • Computer Components
        • In-depth Explanations
      • File Maintenance
      • Computer & Safety
      • Software Development
      • Bits & Binary
    • Careers related to Computer Science
    • Postsecondary Opportunities
Powered by GitBook
On this page
  • Goal
  • Problem Constraints
  • Problem Requirement Breakdown
  • Possible Solutions
  • Connected Readings
  1. Python Programming
  2. Competitive Programming

Longest Common Prefix - LeetCode

PreviousSubtract each value from the target, see if the difference exists in the listNextCompare all possible prefixes

Last updated 10 months ago

Goal

Our goal in this chapter is to analyze a string related competitive programming problem to breakdown the requirements for a solution.

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.

Problem Constraints

Constraints (what our possible test cases will be):

  • Number of different words -> 1 <= words.length <= 200

  • The word length of each words -> 0 <= words[i].length <= 200

  • Each word in our dataset will consists of only lowercase English letters or an empty string.

Problem Requirement Breakdown

    • A list of strings

  • Compare different prefixes to find matching patterns

  • Return a common prefix if found, otherwise return an empty string

Possible Solutions

  1. Compare all possible prefixes

  • Grab the first word of the dataset

    • We will be creating all possible for prefixes from this word

  • Compare the rest of the dataset and see if the first word's prefixes can be a prefix from each word in the dataset

    • If so, return the longest prefix

  1. Create the longest common prefix with the direct neighbour

  • Assume that the longest prefix is the first word of the dataset

  • Compare that second word in the list with the current long prefix and create a new longest prefix possible

  • Do this with each subsequent neighbours

  • At any point the longest prefix is empty, return empty string

  • If there are no more neighbours, return the prefix

  1. Look at each strings vertically to see if they match

0 1 2 3 4 5 6
f l o w
f l o w e r
f l o w e r s

Connected Readings

Create a that takes a single argument:

Functions ()

Loops ()

List ()

Strings ()

🐍
The Problem
function
Link
Link
Link
Link