Methode über Leerzeichen

[ocsme]

Guten Tag,

hier erstmal die Aufgabenstellung:

Schreiben Sie eine effiziente Methode, die die Länge der längsten Sequenz von
Leerzeichen in einem gegebenen String sucht und dabei möglichst wenig Zeichen im
String untersucht (Hinweis: Das Programm sollte schneller werden, wenn die Länge
der Sequenz von Leerzeichen zunimmt). Geben Sie außerdem die Zahl der
benötigten Vergleiche aus.

Das Thema hatte ich hier schon mal da wurde es über Binäresuche gelöst. Ich habe aber einen neuen Ansatz denn auch Ich hin bekomme bis jetzt

Ich fülle einen String mit Leerzeichen und vergleiche diese dann ob die Anzahl der Leerzeichen im String vorhanden sind. Mein Programm sieht bis jetzt so aus:

public class WhiteSpace {
   
    static boolean fault(String text) {
        return (text==null || text.length()==0);
    }
   
    static void lengthWhiteSpace(String text) {
        int vergleiche=0, sequenz=0;
       
        System.out.println(text.length());
               
        if(fault(text)) {
            sequenz=0;
            vergleiche=0;
        }
       
        if(!fault(text)) {
            String s="";
            for(int i=text.length();i>0;i--) {
                s+=" ";
                if(text.contains(s)) {
                    sequenz=s.length();
                    vergleiche++;
                }
            }
        }
       
        System.out.println("Vergleiche " + vergleiche);
        System.out.println("Sequenz " + sequenz);
    }
   
    public static void main(String[] args) {
        String text="adsf    adsfsafasdf      dsaf";
        lengthWhiteSpace(text);
       
    }
}

Mein Problem sind die Vergleiche.
Die Sequenz stimmt ja damit da ich durch den String laufe und die Anzahl immer wieder erhöhe vorher habe ich gefragt ob der String Null ist oder leer ist!
Wie bekomme ich das nun aber mit den Vergleichen hin?
Hat da vielleicht jemand eine Idee?

LG

 

[Javinner]

Ich glaube, du musst den String mit dem Leerzeichen spliten, dann hast du ja die Anzahl der Elemente in dem String-Array, das dann verrechnen, fertig.

 

[ocsme]

ich glaube ich verstehe dich nicht so recht.
Meinst du etwas ich soll ein String Array erstellen dort dann 1,2,3,4,5,... etc. Leerzeichen abspeichern lassen mit einer Schleife so lange bis ich die Länge des übergebenen Strings habe.
Dann vergleiche ich jede Position also im String Array [0] = 1 Leerzeichen mit meinem übergebenen String und so weiter?
Dann hätte man die Antwort auch also Anzahl der vergleiche aber ist das nicht mega viel Aufwand?
LG

 

[ocsme]

Hab es mal schnell runter gecodet so wie ich es meine vielleicht kann man das eher verstehen als der Text

int length=text.length();
        String[] s = new String[length];
        for(int i=0;i<s.length;i++) {
            String test="";
            for(int j=0;j<=i;j++) {
                test+=" ";
            }
            s[i]=test;
        }
      
        for(int i=0;i<s.length;i++)
            System.out.println(s[i]);

Jetzt habe ich ein String Array mit Leerzeichen

 

[Javinner]

aber ist das nicht mega viel Aufwand?

Vier Zeilen Schau dir die Klasse String an, speziell die Methode split(Variable)

 

[Javinner]

public class SplitTheString
{

  
    public static void main(String[] args)
    {
        String zweiLeerZeichen = "- - -";
        System.out.println(leerzeichen(zweiLeerZeichen));
      
        String dreiLeerZeichen = " - - -";
        System.out.println(leerzeichen(dreiLeerZeichen));
      
        String vierLeerZeichen = "- - - - ";
        System.out.println(leerzeichen(vierLeerZeichen));
      
        String fuenfLeerZeichen = " - - - - ";
        System.out.println(leerzeichen(fuenfLeerZeichen));
    }

    public static int leerzeichen(String toCheck)
    {
          //Dein Code
    }

}
/** Output */
2
3
4
5

http://openbook.rheinwerk-verlag.de/javainsel9/javainsel_04_008.htm

 

[ocsme]

so hab ich es nun gelöst.

        String text="iitextiiiiiiiiiiiiiiiitext";
        lengthWhiteSpace(text);
       
        int vergleich=0;
        boolean gefunden=true;
        int length=text.length();
       
        String[] s = new String[length];
        for(int i=0;i<s.length;i++) {
            String tmp="";
            for(int j=0;j<=i;j++) {
                tmp+="i";
            }
            s[i]=tmp;
        }

       
        for(int i=s.length-1;i>=0;i--)
            if(text.contains(s[i])&&gefunden) {
                System.out.println(s[i]);
                vergleich=text.length()-i-1;
                gefunden=false;
            }
       
        System.out.println(vergleich);

Leider verstehe ich nicht so ganz wie das mit dem split gehen soll
ich werde mir das nochmal genauer anschauen doch was bringt mir das überhaupt?
LG

 

[JCODA]

Ich glaube ihr überseht eine wichtige Sache an der Aufgabenstellung.
Zuerst mal: ein split ist ja nicht besser (bzgl. den benötigten Vergleichen) als brute-force. (Einmal über String iterieren und zusammenhängende Leerzeichen zählen)
Wenn man während der Iteration weiß, dass die bisherig längste Sequenz 3 lang war. Dann kann ich beim letzten Buchstaben, der kein Leerzeichen war 3 weiter springen, und schauen, ob ein Leerzeichen vorliegt. d.h. ich im Fall dass eins vorliegt, muss ich nochmal zurück. Falls es aber kein Leerzeichen war, kann ich getrost weitersuchen, weil die Sequenz kann ja nicht länger als 3 an dieser Stelle werden. (Das ganze gibt es als dynamischen Programmierungs-Algo, allerdings hab ich den speziellen Namen gerade nicht parat.)

 

[Javinner]

public class SplitTheString
{

  
    public static void main(String[] args)
    {
        String zweiLeerZeichen = "- - -";
        System.out.println(leerzeichen(zweiLeerZeichen));
       
        String dreiLeerZeichen = " - - -";
        System.out.println(leerzeichen(dreiLeerZeichen));
       
        String vierLeerZeichen = "- - - - ";
        System.out.println(leerzeichen(vierLeerZeichen));
       
        String fuenfLeerZeichen = " - - - - ";
        System.out.println(leerzeichen(fuenfLeerZeichen));
    }

    public static int leerzeichen(String toCheck)
    {
        int x;
        String[] array = toCheck.split(" ");
        x = array.length;
        x = toCheck.charAt(toCheck.length() - 1) == ' ' ? (x):(x -= 1);
        return x;
    }

}

 

[Javinner]

doch was bringt mir das überhaupt?

Die Probleme, die du hast, hat in der Vergangenheit schon jemand gelöst. Erweitere doch dein Horizont durch die Vielfalt der verschiedenen Klassen und deine Werkzeugkiste wird mit der Zeit größer und besser

 

[Javinner]

ein split ist ja nicht besser

Ich finde, dass der Split sehr übersichtlich ist und eine Menge an Tipparbeit abnimmt. Wer die Klasse String kennt, sollte sich für ihre Methoden interessieren, vor allem als Anfänger

 

[JCODA]

Ich finde, dass der Split sehr übersichtlich ist und eine Menge an Tipparbeit abnimmt. Wer die Klasse String kennt, sollte sich für ihre Methoden interessieren, vor allem als Anfänger

Natürlich. Programmierer sollten immer "das Rad nicht neu erfinden".

Man muss aber schauen, ob die Lösung das Problem tatsächlich löst:
Möchte man nur eine funktionierende Lösung oder eine performante. ( Insbesondere eine die, die Anforderung in der Aufgabenstellung erfüllt )

 

[ocsme]

Danke erstmal
Ich mache die Sachen gerne selbst das ist meine Übung!
Klar ist es später besser die Methoden der String Klasse zu kennen und sowas dann darüber zu machen. Leider hatte ich bis jetzt noch nicht so sehr die Zeit mich damit auseinander zu setzen vielleicht liegt es auch daran das ich immer wieder alles selbst schreibe und so lange an den Aufgaben sitze

Javinner ist damit die Aufgabe erfüllt? Das mit dem Splitt verstehe ich nicht so wirklich wie schon gesagt werde ich mir wieder anschauen.
Ich hab ja eigentlich nur noch die Vergleiche benötigt die ich ja nun auch hin bekommen habe. So gesehen wird das Programm nicht schneller es ist ein "Pseudo Vergleich" da ich einen String oder gar ein String Array fülle mit leer Zeichen und diese mit dem gegebenen String vergleiche. Es wird nur dann schneller wenn mehr Leerzeichen drin sind als 1 denn dann habe ich ja 1 Vergleich weniger denn ich machen muss etc.!

Danke erstmal

LG

 

[mihe7]

fülle mit leer Zeichen und diese mit dem gegebenen String vergleiche.

Bei der Aufgabe kommt es sehr darauf an, was man als "Vergleich" zählt. Ich würde sagen, dass damit jeder Vergleich eines Zeichens der Zeichenkette mit einem beliebigen Zeichen gemeint ist. In dem Fall hast Du sehr viele Vergleiche, weil Dein String-Vergleich ja selbst Zeichen miteinander vergleicht.

Ich werfe mal folgende Lösung in den Raum:

public class Test {
    private int max;
    private int vergleiche;
    private String str;
    private int len;

    public Test(String str) {
        this.str = str;
        this.len = str.length();
    }

    public void zaehle() {
        vergleiche = 0;
        max = 0;
        int lastNonSpace = -1;
        int i = 0;
        while (i < len) {
            if (isSpace(i)) {
                int bs = beginnSequenz(i, lastNonSpace);
                int es = endeSequenz(i+1);
                lastNonSpace = es;
                int sl = es - bs;
                max = Math.max(max, sl);
                i = es;
            } else {
                lastNonSpace=i;
            }         
            i += max + 1;
        }
    }

    private int beginnSequenz(int ix, int lastNonSpace) {
        while (ix > lastNonSpace+1 && isSpace(ix-1)) {
            ix--;
        }
        return ix;       
    }

    private int endeSequenz(int ix) {
        while (ix < len && isSpace(ix)) {
            ix++;
        }
        return ix;
    }

    private boolean isSpace(int ix) {
        vergleiche++;
        return str.charAt(ix) == ' ';
    }

    public static void main(String[] args) throws Exception {
        Test ws = new Test("AB     ABDEFGB C");
        ws.zaehle();
        System.out.printf("Maximale Länge: %d, Vergleiche %d\n", ws.max, ws.vergleiche);
    }
}