algoadvance

Leetcode 1961. Check If String Is a Prefix of Array

Problem Statement

You are given a string s and an array of strings words. You need to determine if s is a prefix of the concatenation of all the strings in words.

A string s is a prefix of a string t if t starts with the string s.

Example 1:

Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"]
Output: true
Explanation:
s starts with "i".
s. then, equals "i"+"love" (i.e "ilove").
s. then, equals "i"+"love"+"leetcode" (i.e "iloveleetcode").

Example 2:

Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"]
Output: false
Explanation:
s does not start with "apples".

Clarifying Questions

  1. What is the expected input size for s and words?
    • This will help understand if any performance optimization is needed.
  2. Can words contain empty strings or s be an empty string?
    • Edge cases handling.
  3. Are all characters ASCII or can they be Unicode?
    • Determines if we need to handle any special character encoding issues.
  4. Is there a constraint on the lengths of the strings inside words?
    • Helps understand if individual string processing is required or handling their concatenation directly is sufficient.

Code

public class Solution {
    public boolean isPrefixString(String s, String[] words) {
        StringBuilder concatenated = new StringBuilder();
        
        for (String word : words) {
            concatenated.append(word);
            // If concatenated string equals s up to its length, it is a prefix
            if (concatenated.length() >= s.length()) {
                return concatenated.toString().startsWith(s);
            }
        }
        
        return false; // If loop completes and no match was found
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Example 1:
        String s1 = "iloveleetcode";
        String[] words1 = {"i", "love", "leetcode", "apples"};
        System.out.println(solution.isPrefixString(s1, words1));  // Output: true
        
        // Example 2:
        String s2 = "iloveleetcode";
        String[] words2 = {"apples", "i", "love", "leetcode"};
        System.out.println(solution.isPrefixString(s2, words2));  // Output: false
    }
}

Strategy

  1. Initialization:
    • Use a StringBuilder to efficiently concatenate the strings from the words array.
  2. Concatenate words:
    • Loop through each word in the words array, appending them to the StringBuilder.
  3. Check prefix condition:
    • After each concatenation, check if the current state of the concatenated string matches the prefix condition for s up to its length.
  4. Break early:
    • If at any point the length of the concatenated string is equal to or exceeds that of s, check if it starts with s. If it does, return true. If the concatenated string surpasses the length of s without matching, it will return false.
  5. Edge case:
    • If the loop completes without satisfying the condition, return false.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI