Backtracking/src/main/java/de/hsrm/ads/Reverse.java at master · luca910/Backtracking · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
package de.hsrm.ads;

/**
 * String Reverse Rekusiv mit Palindrom-Check
 * @see <a href="https://www.cs.hs-rm.de/~reith/resources/Lehre/ADS22/Test2.pdf">cs.hs-rm.de</a>
 * @author Luca Krawczyk
 * @author Paul Knoll
 *
 * @version 1.0
 *
 * Creates a new Reverse object.
 */
public class Reverse {
    /**
     * Kehrt den Übergebenen String um.
     *
     * Rekurrenz:
     *  f(n) = 1 + f(n-1)
     *  f(0) = 1
     *  f(1) = 1
     *  f(2) = 2
     *  f(3) = 3
     *  ...
     *  f(n) = n
     *
     * @param s String to reverse
     * @return reversed string
     */
    public String reverseRecursive(String s) {
        if (s.length() == 0) {
            return s;
        }
        return reverseRecursive(s.substring(1)) + s.charAt(0);
    }

    /**
     * Kehrt den Übergebenen String um prüft zuvor ob es sich um einen Palindrom handelt.
     *
     * @param s String to reverse
     * @return reversed string
     */
    public String reverseRecursivePalindrome(String s) {
        if (isPalindrome(s)) {
            return s;
        }
        if (s.length() == 0) {
            return s;
        }
        return reverseRecursivePalindrome(s.substring(1)) + s.charAt(0);
    }

    /**
     * Prüft ob ein String ein Palindrom ist.
     *
     * @param s String to check
     * @return true if string is palindrome
     */

    public boolean isPalindrome(String s) {
        if (s.length() == 0) {
            return true;
        } else {
            for (int i = 0; i < s.length() / 2; i++) {
                if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Hauptmethode zum Starten des Backtracking Algorithmus.
     * @param args keine Argumente
     */
    public static void main(String[] args) {
        long ticks;
        long startTime = System.nanoTime();
        long stopTime = System.nanoTime();//

        Reverse r = new Reverse();
        String s= "leohortetrohoel";
        String s2= "Xylophone";

        startTime = System.nanoTime();
        System.out.print(r.reverseRecursive(s));
        stopTime = System.nanoTime();
        System.out.println(" (Warmup-run)");
        ticks = (stopTime - startTime) / 1000;
        System.out.println("Zeit: " + (stopTime - startTime) + "ns ca.:" + String.format("%d.%02d", ticks / 1000, (ticks % 1000) / 10) + "ms\n");

        startTime = System.nanoTime();
        System.out.print(r.reverseRecursivePalindrome(s));
        stopTime = System.nanoTime();
        System.out.println(" (Palindrom-Check)");
        ticks = (stopTime - startTime) / 1000;
        System.out.println("Zeit: " + (stopTime - startTime) + "ns ca.:" + String.format("%d.%02d", ticks / 1000, (ticks % 1000) / 10) + "ms\n");

        startTime = System.nanoTime();
        System.out.println(r.reverseRecursive(s));
        stopTime = System.nanoTime();
        ticks = (stopTime - startTime) / 1000;
        System.out.println("Zeit: " + (stopTime - startTime) + "ns ca.:" + String.format("%d.%02d", ticks / 1000, (ticks % 1000) / 10) + "ms\n");

        startTime = System.nanoTime();
        System.out.println(r.reverseRecursivePalindrome(s2));
        stopTime = System.nanoTime();
        ticks = (stopTime - startTime) / 1000;
        System.out.println("Zeit: " + (stopTime - startTime) + "ns ca.:" + String.format("%d.%02d", ticks / 1000, (ticks % 1000) / 10) + "ms\n");

        startTime = System.nanoTime();
        System.out.println(r.reverseRecursive(s2));
        stopTime = System.nanoTime();
        ticks = (stopTime - startTime) / 1000;
        System.out.println("Zeit: " + (stopTime - startTime) + "ns ca.:" + String.format("%d.%02d", ticks / 1000, (ticks % 1000) / 10) + "ms\n");


    }
}