Four Strings Square

Arrange four strings of equal length around a square matrix such that the last character of one string matches the first character of the next string in the sequence

Understand the Problem

Problem Statement

Four strings of equal length L are provided as input. These strings must be arranged to form an L×L square matrix. The first string in the input always represents the top side of the square. The remaining three strings can appear in any order in the input, but they must be arranged correctly around the square.

The arrangement is determined by the fact that the last character of one string must match the first character of the next string in the sequence. You can assume that each character appears only once as a connecting point between strings.

Print the L×L square matrix with the four strings positioned around the perimeter, with asterisks (*) filling the interior positions.

Constraints

3 ≤ L ≤ 100 (length of each string)
All four strings have exactly the same length L
Each string contains only uppercase letters
The last character of each string will be unique and will appear as the first character of exactly one other string
The first string in input always represents the top side of the square

Examples

Example 1

Input

TIGER
YACHT
RANGE
EVERY

Output

TIGER
H***A
C***N
A***G
YREVE

Explanation

The strings are arranged as follows: - Top: TIGER - Right: YACHT (H is at bottom-right, matches with T from TIGER) - Bottom: EVERY (reversed as YREVE, Y connects to H from YACHT) - Left: RANGE (reversed as EGNAR, E connects to Y from EVERY) Interior positions are filled with asterisks (*)

Example 2

Input

MAN
DOT
NOD
TIM

Output

MAN
I*O
TOD

Explanation

The strings are arranged as follows: - Top: MAN - Right: TIM (M connects to N from MAN) - Bottom: DOT (reversed as TOD, T connects to M from TIM) - Left: NOD (reversed as DON, D connects to T from DOT) Since L=3, there's only one interior position filled with *

Solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    char s1[101], s2[101], s3[101], s4[101];
    scanf("%s", s1);
    scanf("%s", s2);
    scanf("%s", s3);
    scanf("%s", s4);
    
    int l = strlen(s1);
    char *words[4];
    words[0] = s1;
    
    // Find the sequence by matching characters
    int idx = 1;
    char lastChar = s1[l-1];
    
    while (idx < 4) {
        if (words[idx-1][l-1] == s2[0]) {
            words[idx] = s2;
        } else if (words[idx-1][l-1] == s3[0]) {
            words[idx] = s3;
        } else if (words[idx-1][l-1] == s4[0]) {
            words[idx] = s4;
        } else {
            // Find string whose last char matches first char of words[idx-1]
            if (s2[l-1] == words[idx-1][0]) words[idx] = s2;
            else if (s3[l-1] == words[idx-1][0]) words[idx] = s3;
            else if (s4[l-1] == words[idx-1][0]) words[idx] = s4;
        }
        idx++;
    }
    
    // Create the pattern matrix
    char pattern[100][100];
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < l; j++) {
            pattern[i][j] = '*';
        }
    }
    
    // Fill the top side
    for (int i = 0; i < l; i++) {
        pattern[0][i] = words[0][i];
    }
    
    // Fill the right side
    for (int i = 0; i < l; i++) {
        pattern[i][l-1] = words[1][i];
    }
    
    // Fill the bottom side (reversed)
    for (int i = 0; i < l; i++) {
        pattern[l-1][i] = words[2][l-1-i];
    }
    
    // Fill the left side (reversed)
    for (int i = 0; i < l; i++) {
        pattern[i][0] = words[3][l-1-i];
    }
    
    // Print the result
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < l; j++) {
            printf("%c", pattern[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

Time:O(L²) where L is the length of each string. The main operations are filling the L×L matrix and printing it.

Space:O(L²) for the pattern matrix of size L×L.

Approach:

The C solution follows these steps:

Input Reading: Read all four strings using scanf.
Sequence Building: Use character matching to determine the correct order of strings around the square.
Matrix Initialization: Create a 2D character array filled with asterisks.
Perimeter Filling: Place each string along its respective side:
- Top: words[0] placed normally from left to right
- Right: words[1] placed normally from top to bottom
- Bottom: words[2] placed in reverse from right to left
- Left: words[3] placed in reverse from bottom to top
Output: Print the completed matrix row by row.

Visual Explanation

Loading diagram...

All Problems