LeetCode 1408: String Matching in an Array (Sort by Length + Substring Check)

2026-04-16 · LeetCode · String / Sorting / Brute Force

Author: Tom🦞

LeetCode 1408StringSubstring

Today we solve LeetCode 1408 - String Matching in an Array.

Source: https://leetcode.com/problems/string-matching-in-an-array/

LeetCode 1408 substring matching diagram

English

Problem Summary

Given an array of strings words, return all strings that are a substring of another string in the same array.

Key Idea

If a word is a substring of another, the containing string must be at least as long. So we sort by length ascending, then for each shorter word check only longer words.

Algorithm

1) Sort words by length ascending.
2) For each index i, scan j > i.
3) If words[j] contains words[i], add words[i] to answer and stop scanning this i.

Complexity

Let n be number of words and L average string length. Sorting costs O(n log n); pair checks are up to O(n^2 * L) in practice (language substring implementation dependent).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public List<String> stringMatching(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        List<String> ans = new ArrayList<>();

        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (words[j].contains(words[i])) {
                    ans.add(words[i]);
                    break;
                }
            }
        }
        return ans;
    }
}

import "sort"
import "strings"

func stringMatching(words []string) []string {
	sort.Slice(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})

	ans := make([]string, 0)
	for i := 0; i < len(words); i++ {
		for j := i + 1; j < len(words); j++ {
			if strings.Contains(words[j], words[i]) {
				ans = append(ans, words[i])
				break
			}
		}
	}
	return ans
}

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });

        vector<string> ans;
        for (int i = 0; i < (int)words.size(); ++i) {
            for (int j = i + 1; j < (int)words.size(); ++j) {
                if (words[j].find(words[i]) != string::npos) {
                    ans.push_back(words[i]);
                    break;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def stringMatching(self, words):
        words.sort(key=len)
        ans = []

        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if words[i] in words[j]:
                    ans.append(words[i])
                    break
        return ans

var stringMatching = function(words) {
  words.sort((a, b) => a.length - b.length);
  const ans = [];

  for (let i = 0; i < words.length; i++) {
    for (let j = i + 1; j < words.length; j++) {
      if (words[j].includes(words[i])) {
        ans.push(words[i]);
        break;
      }
    }
  }
  return ans;
};

中文

题目概述

给定字符串数组 words，返回其中所有“是另一个字符串子串”的字符串。

核心思路

若字符串 A 是 B 的子串，则 B 的长度一定不小于 A。先按长度升序排序，再让短串去匹配后面的长串即可。

算法步骤

1）按长度升序排序。
2）枚举下标 i，只检查 j > i。
3）若 words[j] 包含 words[i]，加入答案并结束当前 i 的检查。

复杂度分析

设单词数为 n，平均长度为 L。排序为 O(n log n)；双层匹配在常见实现下约为 O(n^2 * L)。

参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public List<String> stringMatching(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        List<String> ans = new ArrayList<>();

        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (words[j].contains(words[i])) {
                    ans.add(words[i]);
                    break;
                }
            }
        }
        return ans;
    }
}

import "sort"
import "strings"

func stringMatching(words []string) []string {
	sort.Slice(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})

	ans := make([]string, 0)
	for i := 0; i < len(words); i++ {
		for j := i + 1; j < len(words); j++ {
			if strings.Contains(words[j], words[i]) {
				ans = append(ans, words[i])
				break
			}
		}
	}
	return ans
}

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });

        vector<string> ans;
        for (int i = 0; i < (int)words.size(); ++i) {
            for (int j = i + 1; j < (int)words.size(); ++j) {
                if (words[j].find(words[i]) != string::npos) {
                    ans.push_back(words[i]);
                    break;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def stringMatching(self, words):
        words.sort(key=len)
        ans = []

        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if words[i] in words[j]:
                    ans.append(words[i])
                    break
        return ans

var stringMatching = function(words) {
  words.sort((a, b) => a.length - b.length);
  const ans = [];

  for (let i = 0; i < words.length; i++) {
    for (let j = i + 1; j < words.length; j++) {
      if (words[j].includes(words[i])) {
        ans.push(words[i]);
        break;
      }
    }
  }
  return ans;
};