[Leetcode] – Word Break Solution

    by nikoo28

    In the given problem statement, we have a string s and a dictionary wordDict containing a list of words. We need to determine if s can be segmented into a space-separated sequence of dictionary words.

    The tricky part of this problem is ensuring that every segment of the string matches words from the dictionary. A brute-force approach could generate all possible segmentations, but that would be highly inefficient.

    Input: s = "studyalgorithms"
    wordDict = ["study", "algorithms"]
    Output: true
    Explanation: Since "studyalgorithms" can be split into "study" and "algorithms", both of which are in the dictionary, the function should return true.
    Input: s = "catsandog", 
    wordDict = ["cats","dog","sand","and","cat"]
    Output: false
    Explanation: No possible combination of the dictionary words can be combined to get s. Full words are to be used
    Fig: Possible word break can’t get the combination right

    Brute Force Approach

    The brute force approach involves checking all possible partitions of the string and verifying if each segment exists in the dictionary.

    • Generate all possible segmentations of the string.
    • For each segmentation, check if all the words exist in the dictionary.
    • If a valid segmentation is found, return true.
    • If no segmentation matches, return false.

    This approach has a time complexity of O(2^n) due to the exponential number of possible partitions, making it impractical for large inputs.

    Optimized Dynamic Programming Approach

    To efficiently solve this problem, dynamic programming is used. The idea is to use a boolean array dp where dp[i] indicates whether the substring s[0..i] can be segmented using words from the dictionary.

    Steps:

    • Convert the dictionary into a set for O(1) lookups.
    • Compute the maximum word length from the dictionary to optimize substring checks.
    • Create a boolean array dp of size n+1 (where n is the length of s), initialized to false except dp[0], which is true (an empty string is always valid).
    • Iterate over the string s and check for valid word breaks using dictionary words.
    • Update dp[i] if a valid segmentation is found.
    • The final answer is stored in dp[n].
    word break for edge cases
    Fig: Word Break using a dynamic programming

    Code

      boolean wordBreak(String s, List<String> wordDict) {
    
        // Convert the dictionary to a set for O(1) lookups
        Set<String> wordSet = new HashSet<>(wordDict);
    
        // Find the maximum word length in the dictionary
        int maxLen = 0;
        for (String word : wordDict) {
          maxLen = Math.max(maxLen, word.length());
        }
    
        int n = s.length();
        // dp[i] states if the substring s[0..i] can be segmented
        boolean[] dp = new boolean[n + 1];
    
        // Base case: empty string is valid
        dp[0] = true;
    
        for (int i = 1; i <= n; i++)
    
          // Check prefixes of length up to maxLen
          for (int j = i - 1; j >= Math.max(0, i - maxLen); j--)
            if (dp[j] && wordSet.contains(s.substring(j, i))) {
              dp[i] = true;
              break; // No need to check further prefixes
            }
    
        return dp[n];
      }
    Code language: Java (java)

    Time Complexity: O(n * maxLen), where n is the length of s and maxLen is the length of the longest word in the dictionary. Each substring check is optimized by restricting it to maxLen.
    Space Complexity: O(n), used by the dp array.

    By using dynamic programming, we significantly optimize the solution compared to brute force. The use of a dictionary set for lookups and limiting substring checks improves efficiency. This approach ensures that we can determine whether a string can be segmented efficiently, even for large inputs.

    Video Explanation:

    YouTube player
    0 comments
    0 FacebookTwitterLinkedinWhatsappEmail
  • Arrays

    [Leetcode] – Insert Interval Solution

    by nikoo28
    4 minutes read

    In this problem, we are given a list of non-overlapping intervals sorted by their start times, along with a new interval. The goal is to insert the new interval into the list while ensuring the intervals remain non-overlapping and sorted. If necessary, overlapping intervals should be merged. The tricky part of this problem lies in handling overlapping intervals efficiently while maintaining the sorted order. We also need to consider edge cases, such as when the new interval does not overlap with any existing intervals or when it encompasses multiple intervals. …

    0 FacebookTwitterLinkedinWhatsappEmail
  • System DesignTheory

    Message Queue in System Design

    by nikoo28
    3 minutes read

    Continuing with our System Design series we’ll be discussing message queue, an essential component in building scalable, decoupled systems. Message queues help systems handle communication between different parts asynchronously, ensuring smooth data flow even during heavy traffic. What is a Message Queue? A message queue is a system that allows different parts of a system to communicate with each other in an asynchronous manner. It acts as a buffer between a producer (the part that sends messages) and a consumer (the part that processes messages), allowing the producer to continue …

    0 FacebookTwitterLinkedinWhatsappEmail
  • System DesignTheory

    Proxy in System Design

    by nikoo28
    5 minutes read

    Let’s continue the journey in System Design. In this post, we’ll explore the concept of forward and reverse proxy, which play a crucial role in optimizing and securing web traffic. Proxies act as intermediaries, improving efficiency, security, and management of requests between clients and servers. What is a Proxy? A proxy is essentially an intermediary that sits between a client and a server, forwarding requests and responses between the two. It can be used for various purposes such as load balancing, security, caching, and more. Real-World Example: Imagine a bookstore …

    0 FacebookTwitterLinkedinWhatsappEmail
  • System DesignTheory

    Indexing in System Design

    by nikoo28
    3 minutes read

    Let us continue our System Design series! In this post, we’ll dive into the concept of indexing in databases. Indexing is a technique that allows for faster data retrieval by organizing and optimizing the way data is stored. What is Indexing? Indexing is like creating a shortcut for finding the right data quickly. Instead of scanning the entire database, the index helps you jump directly to the location of the data you need, improving the performance of your queries. Real-World Example: Let’s go back to our bookstore analogy. Imagine you …

    0 FacebookTwitterLinkedinWhatsappEmail
  • System DesignTheory

    Databases in System Design

    by nikoo28
    5 minutes read

    Welcome again to System Design series! In this post, we will explore the concept of databases, which are fundamental to storing, organizing, and managing data in any application. Databases are the backbone of any data-driven system, providing the infrastructure needed to handle, retrieve, and manipulate data efficiently. What is a Database? A database allows users to easily access, manage, and update a structured collection of data. It serves as a digital ledger, storing information in an organized way, allowing quick retrieval and manipulation of data. Real-World Example: In our bookstore …

    0 FacebookTwitterLinkedinWhatsappEmail
  • System DesignTheory

    Caching in System Design

    by nikoo28
    6 minutes read

    Welcome back to the System Design series! In this post, we will explore the concept of caching, a powerful technique used to enhance the speed and performance of applications. Caching plays a critical role in optimizing data retrieval and ensuring a smooth user experience. What is Caching? Caching is a technique where systems store frequently accessed data in a temporary storage area, known as a cache, to quickly serve future requests for the same data. This temporary storage is typically faster than accessing the original data source, making it ideal …

    0 FacebookTwitterLinkedinWhatsappEmail

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More