Given a String, the task it to split the String into a number of substrings.
A String in java can be of 0 or more characters.
Examples :
(a) "" is a String in java with 0 character (b) "d" is a String in java with 1 character (c) "This is a sentence." is a string with 19 characters.
Substring: A String that is a part of another string is called substring of the other string.
Example 1: Let us consider the string bat. The possible substrings are:
(1) "b" (2) "ba" (3) "bat", every string is a substring of itself (4) "a" (5) "at" (6) "t" (7) "" , "" is a substring of every string
Example 2: Let us consider the string The Cat. The possible substrings are:
(1) "T" (2) "Th" (3) "The" (4) "The " (5) "The C" (6) "The Ca" (7) "The Cat", every string is a substring of itself (8) "h" (9) "he" (10) "he " (11) "he C" (12) "he Ca" (13) "he Cat" (14) "e" (15) "e " (16) "e C" (17) "e Ca" (18) "e Cat" (19) " " (20) " C" (21) " Ca" (22) " Cat" (23) "C" (24) "Ca" (25) "Cat" (26) "a" (27) "at" (28) "t" (29) "" , "" is a substring of every string
Note: Total number of substrings of a string of length N is (N * (N + 1)) / 2. This is after excluding the empty string “” because it is a substring of all strings.
Approach:
Let us consider a string which has n characters:
1. For each character at index i (0 to n-1):
find substrings of length 1, 2, ..., n-i
Example: Let our string be cat, here n = 3 (the length of string)
here,
index of 'c' is 0
index of 'a' is 1
index of 't' is 2
Loop from i = 0 to 2: (since n-1 = 2)
When i = 0:
Substring of length 1 : "c"
Substring of length 2 : "ca"
Substring of length 3 : "cat" , (substring of length n-i or 3-0 = 3)
When i = 1:
Substring of length 1 : "a"
Substring of length 2 : "at" , (substring of length n-i or 3-1 = 2)
When i = 2:
Substring of length 1 : "t" , (substring of length n-i or 3-2 = 1)
Example:
Java
// Java Program to split a string into all possible// substrings excluding the string with 0 characters i.e. "" import java.io.*;import java.util.ArrayList; class SubstringsOfAString { // function to split a string into all its substrings // and return the list as an object of ArrayList public static ArrayList<String> splitSubstrings(String s) { // variables to traverse through the // string int i, j; // to store the length of the // string int stringLength = s.length(); // List object to store the list of // all substrings of the string s ArrayList<String> subStringList = new ArrayList<String>(); // first for loop for (i = 0; i < stringLength; i++) { for (j = i + 1; j <= stringLength; j++) { subStringList.add(s.substring(i, j)); } } // end of first for loop // returning the list (object // of ArrayList) of substrings // of string s return subStringList; } public static void main(String[] args) { // here "The Cat" is our input string String stringInput = new String("The Cat"); ArrayList<String> subStringList = SubstringsOfAString.splitSubstrings( stringInput); System.out.println( "\nSubstring list printed as an ArrayList : "); System.out.println(subStringList); System.out.println( "\n\nAll substrings printed 1 per line : "); int count = 1; // each substring would be printed // within double quotes for (String it : subStringList) { System.out.println("(" + count + ") \"" + it + "\""); count++; } }} |
Output
Substring list printed as an ArrayList : [T, Th, The, The , The C, The Ca, The Cat, h, he, he , he C, he Ca, he Cat, e, e , e C, e Ca, e Cat, , C, Ca, Cat, C, Ca, Cat, a, at, t] All substrings printed 1 per line : (1) "T" (2) "Th" (3) "The" (4) "The " (5) "The C" (6) "The Ca" (7) "The Cat" (8) "h" (9) "he" (10) "he " (11) "he C" (12) "he Ca" (13) "he Cat" (14) "e" (15) "e " (16) "e C" (17) "e Ca" (18) "e Cat" (19) " " (20) " C" (21) " Ca" (22) " Cat" (23) "C" (24) "Ca" (25) "Cat" (26) "a" (27) "at" (28) "t"
Time Complexity: O(n2) where n is the length of a string
Output 1: When string Input = bat
Substring list printed as an ArrayList : [b, ba, bat, a, at, t] All substrings printed 1 per line : (1) "b" (2) "ba" (3) "bat" (4) "a" (5) "at" (6) "t"
Output 2: When string Input = The Cat
Substring list printed as an ArrayList : [T, Th, The, The , The C, The Ca, The Cat, h, he, he , he C, he Ca, he Cat, e, e , e C, e Ca, e Cat, , C, Ca, Cat, C, Ca, Cat, a, at, t] All substrings printed 1 per line : (1) "T" (2) "Th" (3) "The" (4) "The " (5) "The C" (6) "The Ca" (7) "The Cat" (8) "h" (9) "he" (10) "he " (11) "he C" (12) "he Ca" (13) "he Cat" (14) "e" (15) "e " (16) "e C" (17) "e Ca" (18) "e Cat" (19) " " (20) " C" (21) " Ca" (22) " Cat" (23) "C" (24) "Ca" (25) "Cat" (26) "a" (27) "at" (28) "t"
