Here's an algorithm:
Alphabet: {a,b,c}
Strings: aba ca abb cb
The most complete solution to this is to build a dictionary M, mapping each string onto the letters, that existed in {a,b,c}, which have been occurred once or multiple times. Here, it's not necessary to set the mappings of the duplicate letters, so that the dictionary M will be a rectangular matrix 4 x 3, consisting of the following elements:
a b c
aba : 1, 1, 0
ca : 1, 0, 1
abb : 1, 1, 0
cb : 0, 1, 1
For instance, the string "abb" contains 1 - 'a' and 2 - 'b', such as that the row of matrix M is { 1, 1, 0 }, for which 1 and 1 values are corresponding to letters 'a' and 'b', respectively, and 0 corresponds to the letter 'c', which has not been found in the string "abb".
Next, take the inner product of the matrix M and its transpose, to obtain the symmetric matrix I=MM^T of shape 4 x 4.
I=MM^T (Upper triangular):
0 1 2 0
0 0 1 0
0 0 0 0
0 0 0 0
Finally, check whether at least one element, on the I matrix's diagonal, is equal to 0. If so, the composition does not exist and the result is "FALSE", or "TRUE", unless otherwise.
Here's a code snippet, written in plain C89, illustrating the algorithm, above:
#include <vector>
#include <fstream>
#include <iostream>
int main()
{
const char* filename = "tZwciVLk.txt";
std::ifstream ifs(filename, \
std::ifstream::ios_base::in);
std::vector<std::string> strings;
char* line = (char*)new char[256];
while (ifs.getline(line, 256))
strings.push_back(line);
std::string chars = "abc";
if (strings.size() == 1) {
std::size_t i = 0; bool f = false;
const char* string = \
strings[strings.size() - 1].c_str();
f = strcmp("\0", string) == 0;
while (i < strlen(string) && !f)
f = strchr(chars.data(), string[i++]);
printf("Output: %s\n", f ? "True" : "False");
return 0;
}
int** M = (int**)malloc(strings.size() * sizeof(int*));
int** I = (int**)malloc(strings.size() * sizeof(int*));
std::size_t n = 0;
for (std::size_t i = 0; i < strings.size(); i++) {
M[i] = (int*)malloc(chars.size() * sizeof(int));
const char* s = strings[i].data();
if (strcmp("\0", s) < 0) {
for (std::size_t j = 0; j < chars.size(); j++)
M[n][j] = strchr(s, chars[j]) ? 1 : 0;
n++;
}
}
bool f = true;
for (std::size_t i = 0; i < n && f; i++) {
I[i] = (int*)malloc(strings.size() * sizeof(int));
memset((void*)I[i], 0x00, strings.size() * sizeof(int));
for (std::size_t j = 0; j < n && f; j++) {
for (std::size_t k = 0; k < chars.size(); k++)
I[i][j] += M[i][k] * M[j][k];
}
f = I[i][i] == 0 ? 0 : 1;
}
for (std::size_t i = 0; i < n; i++)
std::cout << strings[i] << " ";
std::cout << std::endl;
std::cout << "Output: " << (f == true ? "True" : "False") << std::endl;
return 0;
}
Outputs:
Alphabet: {a,b,c}
Strings: aba ca abb cb
Output: True
Alphabet: {a,b,c}
Strings: aba ca abb cb d
Output: False
Alphabet: {a,b,c}
Strings: tt yyyy zz dd ppp
Output: False
Alphabet: {a,b,c}
Strings: tt yyyy zz dd ppp
Output: False
Alphabet: {a,b,c}
Strings: xp
Output: False
Alphabet: {a,b,c}
Strings: ax
Output: True
Edit:
Also, this is implementation-specific. You can also find an intersection of the alphabet and each string to do that, something like:
using System.Linq;
char[] chars = {'a','b','c'};
String[] strings = { "aba", "ca", "abb", "cb", "zz" };
bool isComposition(String[] strings, char[] chars) {
return strings.Select(s => s.Intersect(chars).Any()).ToArray().All(s => s);
}
Console.WriteLine(isComposition(strings, chars));
Good Luck! :)