Difference between Subarray, Subsequence, and Subset
本文最后更新于:2023年7月10日 上午
This post will discuss the difference between a subarray, a substring, a subsequence, and a subset.
1. Subarray
A subarray is a slice from a contiguous array (i.e., occupy consecutive positions) and inherently maintains the order of elements. For example, the subarrays of array {1, 2, 3} are {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, and {3}.
Please note that there are precisely n×(n+1)/2 subarrays in an array of size n. Also, there is no such thing as a contiguous subarray. The prefix contiguous is sometimes applied to make the context more clear. So, a contiguous subarray is just another name for a subarray.
code
1 |
|
Output:
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[2]
[2, 3]
[2, 3, 4]
[2, 3, 4, 5]
[3]
[3, 4]
[3, 4, 5]
[4]
[4, 5]
[5]
2. Substring
A substring of a string s is a string s’ that occurs in s. A substring is almost similar to a subarray, but it is in the context of strings.
For example, the substrings of string ‘apple’ are ‘apple’, ‘appl’, ‘pple’, ‘app’, ‘ppl’, ‘ple’, ‘ap’, ‘pp’, ‘pl’, ‘le’, ‘a’, ‘p’, ‘l’, ‘e’, ‘’.
code
1 |
|
Output:
‘t’, ‘te’, ‘tec’, ‘tech’, ‘techi’, ‘techie’, ‘e’, ‘ec’, ‘ech’, ‘echi’, ‘echie’, ‘c’, ‘ch’, ‘chi’, ‘chie’, ‘h’, ‘hi’, ‘hie’, ‘i’, ‘ie’, ‘e’
3. Subsequence
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, {nums, B, D} is a subsequence of sequence {nums, B, C, D, E} obtained after removing {C} and {E}.
People are often confused between a subarray/substring and a subsequence. A subarray or substring will always be contiguous, but a subsequence need not be contiguous. That is, subsequences are not required to occupy consecutive positions within the original sequences. But we can say that both contiguous subsequence and subarray are the same.
In other words, the subsequence is a generalization of a substring, or substring is a refinement of the subsequence. For example, {nums, C, E} is a subsequence of {nums, B, C, D, E}, but not a substring, and {nums, B, C} is both a subarray and a subsequence.
Please note that a subsequence can be in the context of both arrays and strings. Generating all subsequences of an array/string is equivalent to generating a power set of an array/string. For a given set, S, we can find the power set by generating all binary numbers between 0 and 2n-1, where n is the size of the given set.
code
1 |
|
Output:
[‘’, ‘a’, ‘p’, ‘ap’, ‘p’, ‘ap’, ‘pp’, ‘app’, ‘l’, ‘al’, ‘pl’, ‘apl’, ‘pl’, ‘apl’, ‘ppl’, ‘appl’, ‘e’, ‘ae’, ‘pe’, ‘ape’, ‘pe’, ‘ape’, ‘ppe’, ‘appe’, ‘le’, ‘ale’, ‘ple’, ‘aple’, ‘ple’, ‘aple’, ‘pple’, ‘apple’]
4. Subset
A subset is any possible combination of the original set. The term subset is often used for subsequence, but that’s not right. A subsequence always maintains the relative order of the array elements (i.e., increasing index), but there is no such restriction on a subset. For example, {3, 1} is a valid subset of {1, 2, 3, 4, 5}, but it is neither a subsequence nor a subarray.
It is worth noting that all subarrays are subsequences and all subsequences are a subset, but the reverse is not valid. For instance, a subarray {1, 2} of array {1, 2, 3, 4, 5} is also a subsequence and a subset.