Informatica I - Esercizi manipolazione di stringhe e caratteri

Esercizio di laboratorio (impegnativo)

Argomento: Manipolazione di stringhe e caratteri, cicli annidati.

Scrivere un programma che:

• Chiede all'utente di introdurre due stringhe (una per riga), s1 e s2; ciascuna stringa è costituita da tutti i caratteri presenti sulla riga, compresi eventuali spazi iniziali, finali e/o intermedi.
• Verifica se la seconda stringa s2 è una sottosequenza di s1 (al termine della verifica viene visualizzato un messaggio opportuno).

Il programma può usare, della classe String, i soli metodi charAt e length.

Una stringa s2 è una sottosequenza di un'altra stringa s1 se e solo se tutti i caratteri di s2 sono presenti in s1 nello stesso ordine (anche se in posizioni diverse). Ad esempio, gatto è una sottosequenza di gratto, xyz è una sottosequenza di 2xpppyqz, ma yxz non è una sottosequenza di 2xpppyqz.

Ovviamente, una sottostringa è anche una sottosequenza, ma non viceversa.

Soluzione

Ecco una possibile soluzione.

La difficoltà principale di questo esercizio sta non tanto nella scrittura di codice Java quanto nell'ideazione di un algoritmo generale per verificare se una stringa è sottosequenza di un'altra. Leggere con attenzione i commenti per capire come funziona l'algoritmo realizzato nel metodo seqMatch.

import java.util.Scanner;

public class SubsequenceTester{

public static void main(String[] args){

Scanner in = new Scanner(System.in);

System.out.println("Inserire la prima stringa");

String s1 = in.nextLine();

System.out.println("Inserire la seconda stringa");

String s2 = in.nextLine();

if (seqMatch(s1,s2)) //cfr. il metodo seqMatch sotto

System.out.println("E` una sottosequenza");

else System.out.println("Non e` una sottosequenza");

}

Metodo seqMatch

/* Questo metodo verifica se s2 e` una sottosequenza di s1. In caso positivo restituisce il valore true, altrimenti restituisce il valore false.

L'algoritmo realizzato in questo metodo ragiona cosi`: scorriamo i caratteri di s1 finche` non ne troviamo uno che coincide con il primo carattere di s2. Se lo troviamo, allora continuiamo a scorrere i caratteri di s1 finche` non ne troviamo uno che coincide con il secondo carattere di s2. E cosi` via. Se riesco a ripetere questa operazione fino ad arrivare all'ultimo carattere di s2, allora ho dimostrato che s2 e` una sottosequenza di s1*/

public static boolean seqMatch(String s1, String s2){

/* Usiamo due variabili int, i1, e i2, che "puntano" ai caratteri di s1 ed s2, rispettivamente*/

int i2 = 0;

for (int i1 = 0; i1 < s1.length() && i2 < s2.length(); i1++)

if (s1.charAt(i1) == s2.charAt(i2))

i2++;

return i2 == s2.length();

}

}