In this HackerRank Hyper Strings problem solution, we have given a set of Super Strings H, a Hyper String is a string that can be constructed by concatenation of some Super Strings of the set H. We can use each Super String as many times as we want. Given set H, you have to compute the number of Hyper Strings with a length no greater than M.
Problem solution in Python.
#!/bin/python3
import os
import sys
#
# Complete the hyperStrings function below.
#
def hyperStrings(m, H):
modul = 10 ** 9 + 7
letters = "abcdefghij"
H = [hyperstr for hyperstr in H if len(hyperstr) > 0]
H_graded = {letter: [hyper_str for hyper_str in H if hyper_str[-1] == letter] for letter in letters}
letter_graded = {letter : set() for letter in letters}
for letter in letters:
for hyper_end in H_graded[letter]:
letter_graded[letter].add(hyper_end)
for mid in letters:
if mid == hyper_end[0]:
break
to_add = [hyper_beg + hyper_end for hyper_beg in letter_graded[mid]]
if to_add:
letter_graded[letter].update(to_add)
dp = [{letter: 0 for letter in letters} for length in range(m+1)]
dp[0] = {letter: 1 for letter in letters}
for length in range(1, m+1):
for letter, graded in letter_graded.items():
for supstr in graded:
if length < len(supstr):
continue
dp[length][letter] = (dp[length][letter] + dp[length - len(supstr)][supstr[0]]) % modul
for index in range(len(letters) - 1, 0, -1):
dp[length][letters[index - 1]] = (dp[length][letters[index - 1]] + dp[length][letters[index]]) % modul
return sum([dp[length]['a'] for length in range(m + 1)]) % modul
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nm = input().split()
n = int(nm[0])
m = int(nm[1])
H = []
while len(H) < n:
H_item = input().split()
H = H + H_item
result = hyperStrings(m, H)
fptr.write(str(result) + '\n')
fptr.close()
Problem solution in Java.
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
static final int AB = 10;
static final int MAX = 1 << AB;
static final long MOD = 1_000_000_007;
static long hyperStrings(int m, int[] arr) {
Arrays.sort(arr);
boolean[] b = new boolean[MAX];
b[0] = true;
for (int i = 0; i < arr.length; i++) {
int n = 1 << Integer.numberOfTrailingZeros(arr[i]);
for (int j = n-1; j >= 0; j--) {
if (b[j]) {
b[j | arr[i]] = true;
}
}
}
int[] a = new int[MAX];
int n = 0;
for (int i = 0; i < MAX; i++) {
if (b[i]) {
a[n++] = i;
}
}
long result = 0;
int[][] s = new int[a.length+1][AB];
s[0][AB-1] = 1;
for (int i = 0; i < m+1; i++) {
for (int j = 0; j < AB; j++) {
result = (result + s[i][j]) % MOD;
for (int k = 0; k < n; k++) {
int pop = Integer.bitCount(a[k]);
int atz = Integer.numberOfTrailingZeros(a[k]);
if ((i + pop) <= m && atz <= j) {
int alz = Integer.numberOfLeadingZeros(a[k]);
s[i+pop][31 - alz] = (int)((s[i+pop][31 - alz] + s[i][j]) % MOD);
}
}
}
}
return result;
}
static void load(int[] a, int i, char[] arr) {
for (char c : arr) {
a[i] |= 1 << (c - 'a');
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] a = new int[n];
String s = br.readLine();
if (s.contains(" ")) {
String[] v = s.split(" ");
for (int i = 0; i < n; i++) {
load(a, i, v[i].toCharArray());
}
} else {
load(a, 0, s.toCharArray());
for (int i = 1; i < n; i++) {
load(a, i, br.readLine().toCharArray());
}
}
long result = hyperStrings(m, a);
bw.write(String.valueOf(result));
bw.newLine();
br.close();
bw.close();
}
}
Problem solution in C++.
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include<cstdio>
#define REST 1000000007
char S[1000];
int N,M;
char nr[110][110];
int len[110],sol[110];
int lung(char S[100]){
int x=0;
while('a'<=S[x] && S[x]<='z')
++x;
return x;
}
int check(int s1, int poz, int s2){
if(poz+len[s2]-1>len[s1])
return 0;
int k;
for(k=0;k<len[s2];++k){
if(nr[s1][poz+k]!=nr[s2][k+1])
return 0;
}
return 1;
}
void reduc(){
int i,j,k;
char ax[110];
for(i=1;i<=N;++i){
if(len[i]==110)
continue;
for(j=0;j<=len[i];++j)
ax[j]=0;
ax[0]=1;
for(j=1;j<=len[i];++j){
if(!ax[j-1])
continue;
for(k=1;k<=N;++k){
if(k==i || len[k]==110)
continue;
if(check(i,j,k))
ax[j+len[k]-1]=1;
}
}
if(ax[len[i]])
len[i]=110;
}
}
int main(){
int i,j;
scanf("%d%d",&N,&M);
for(i=1;i<=N;++i){
scanf("%s",nr[i]+1);
len[i]=lung(nr[i]+1);
}
reduc();
sol[0]=1;
for(i=0;i<=M;++i){
for(j=1;j<=N;++j){
if(i+len[j]>M)
continue;
sol[i+len[j]]+=sol[i];
if(sol[i+len[j]]>=REST)
sol[i+len[j]]-=REST;
}
}
for(i=1;i<=M;++i){
sol[0]+=sol[i];
if(sol[0]>=REST)
sol[0]-=REST;
}
printf("%d\n",sol[0]);
return 0;
}
Problem solution in C.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
char* readline();
char** split_string(char*, int*);
/*
* Complete the hyperStrings function below.
*/
int hyperStrings(int m, int n, char** H) {
int basicmasks[n];
int low[n];
for(int i = 0; i < n; i++){
basicmasks[i] = 0;
low[i] = H[i][0] - 'a';
int len = strlen(H[i]);
for(int j = 0; j < len; j++){
basicmasks[i] += 1<<(H[i][j] - 'a');
}
}
int masks[1024];
int masklow[1024];
int maskhigh[1024];
int maskbits[1024];
masks[0] = 1;
for(int i = 1; i < 1024; i++){
masks[i] = 0;
for(int j = 0; j < n; j++){
if((i&basicmasks[j]) == basicmasks[j] && (i - basicmasks[j]) < (1<<low[j]) && masks[i - basicmasks[j]] == 1){
masks[i] = 1;
}
}
maskhigh[i] = -1;
masklow[i] = -1;
maskbits[i] = 0;
for(int j = 0; j < 10; j++){
if(((i>>j)&1) == 1){
maskhigh[i] = j;
if(masklow[i] == -1){
masklow[i] = j;
}
maskbits[i]++;
}
}
}
int currnum[m + 1][10];
for(int i = 0; i <= m; i++){
for(int j = 0; j < 10; j++){
currnum[i][j] = 0;
}
}
currnum[0][9] = 1;
for(int i = 1; i <= m; i++){
for(int j = 1; j < 1024; j++){
int prevlen = i - maskbits[j];
if(masks[j] == 1 && prevlen >= 0){
for(int k = masklow[j]; k < 10; k++){
currnum[i][maskhigh[j]] = (currnum[i][maskhigh[j]] + currnum[prevlen][k])%MOD;
}
}
}
}
int total = 0;
for(int i = 0; i <= m; i++){
for(int j = 0; j < 10; j++){
total = (total + currnum[i][j])%MOD;
}
}
return total;
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
int temp;
char** nm = split_string(readline(), &temp);
char* n_endptr;
char* n_str = nm[0];
int n = strtol(n_str, &n_endptr, 10);
if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }
char* m_endptr;
char* m_str = nm[1];
int m = strtol(m_str, &m_endptr, 10);
if (m_endptr == m_str || *m_endptr != '\0') { exit(EXIT_FAILURE); }
char** H = malloc(n * sizeof(char*));
for (int H_itr = 0; H_itr < n;) {
int temp;
char** itemlist = split_string(readline(), &temp);
for(int i = 0; i < temp; i++){
*(H + H_itr) = itemlist[i];
H_itr++;
}
}
int result = hyperStrings(m, n, H);
fprintf(fptr, "%d\n", result);
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
if(data[data_length - 1] != '\0'){
data_length++;
data = realloc(data, data_length);
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str, int* num) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
*num = spaces;
return splits;
}
0 Comments