FilesExpand file tree

 master

/

ShortestPalindrome.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (55 loc) · 1.58 KB

 master

/

ShortestPalindrome.java

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (55 loc) · 1.58 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package string;

/**

* Created by gouthamvidyapradhan on 21/07/2018.

*

* <p>Given a string s, you are allowed to convert it to a palindrome by adding characters in front

* of it. Find and return the shortest palindrome you can find by performing this transformation.

*

* <p>Example 1:

*

* <p>Input: "aacecaaa" Output: "aaacecaaa" Example 2:

*

* <p>Input: "abcd" Output: "dcbabcd"

*

* <p>Solution: O(N ^ 2): for i : (s.length() - 1 -> 0) check if (0, i) is a paliandrome, if not

* append char at i to result string else return string (result + (0, i))

*/

public class ShortestPalindrome {

/**

* Main method

*

* @param args

* @throws Exception

*/

public static void main(String[] args) throws Exception {

System.out.println(new ShortestPalindrome().shortestPalindrome("aaaaaaaaaa"));

}

public String shortestPalindrome(String s) {

if (s.length() == 0 || s.length() == 1) {

return s;

} else if (s.length() == 2) {

if (s.charAt(0) == s.charAt(1)) {

return s;

} else {

return (s.charAt(1) + s);

}

}

if (isPaliandrome(s, 0, s.length() - 1)) return s;

StringBuilder sb = new StringBuilder("");

for (int i = 0, j = s.length() - 1; j >= i; j--) {

if (!isPaliandrome(s, i, j)) {

sb.append(s.charAt(j));

} else {

sb.append(s.substring(0, s.length()));

break;

}

}

return sb.toString();

}

boolean isPaliandrome(String s, int x, int y) {

for (int i = x, j = y; i < j; i++, j--) {

if (s.charAt(i) != s.charAt(j)) return false;

}

return true;

}

}