CPlusPlus/LongestPalindromicSubstringAttempted.rtf at main · shailcompsit/CPlusPlus · 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
{\rtf1\ansi\ansicpg1252\cocoartf2639
\cocoatextscaling0\cocoaplatform0{\fonttbl\f0\fnil\fcharset0 Menlo-Regular;}
{\colortbl;\red255\green255\blue255;\red0\green0\blue255;\red255\green255\blue255;\red0\green0\blue0;
\red32\green108\blue135;\red101\green76\blue29;\red0\green0\blue109;\red19\green118\blue70;\red157\green0\blue210;
\red144\green1\blue18;}
{\*\expandedcolortbl;;\cssrgb\c0\c0\c100000;\cssrgb\c100000\c100000\c100000;\cssrgb\c0\c0\c0;
\cssrgb\c14902\c49804\c60000;\cssrgb\c47451\c36863\c14902;\cssrgb\c0\c6275\c50196;\cssrgb\c3529\c52549\c34510;\cssrgb\c68627\c0\c85882;
\cssrgb\c63922\c8235\c8235;}
\paperw11900\paperh16840\margl1440\margr1440\vieww11520\viewh8400\viewkind0
\deftab720
\pard\pardeftab720\partightenfactor0

\f0\fs26 \cf2 \cb3 \expnd0\expndtw0\kerning0
\outl0\strokewidth0 \strokec2 class\cf0 \strokec4  \cf5 \strokec5 Solution\cf0 \strokec4  \{\cb1 \
\cf2 \cb3 \strokec2 public:\cf0 \cb1 \strokec4 \
\pard\pardeftab720\partightenfactor0
\cf0 \cb3     unordered_map<string, string> stringMap;\cb1 \
\cb3     \cf2 \strokec2 bool\cf0 \strokec4  \cf6 \strokec6 IsPalindrome\cf0 \strokec4 (\cf2 \strokec2 const\cf0 \strokec4  \cf5 \strokec5 string\cf2 \strokec2 &\cf0 \strokec4  \cf7 \strokec7 s\cf0 \strokec4 )\cb1 \
\cb3     \{\cb1 \
\cb3         \cf2 \strokec2 int\cf0 \strokec4  l = \cf8 \strokec8 0\cf0 \strokec4 ;\cb1 \
\cb3         \cf2 \strokec2 int\cf0 \strokec4  r = \cf7 \strokec7 s\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 ()-\cf8 \strokec8 1\cf0 \strokec4 ;\cb1 \
\cb3         \cf9 \strokec9 while\cf0 \strokec4  (l <= r)\cb1 \
\cb3         \{\cb1 \
\cb3             \cf9 \strokec9 if\cf0 \strokec4  (\cf7 \strokec7 s\cf0 \strokec4 [l] == \cf7 \strokec7 s\cf0 \strokec4 [r])\cb1 \
\cb3             \{\cb1 \
\cb3                 ++l;\cb1 \
\cb3                 --r;\cb1 \
\cb3             \}\cb1 \
\cb3             \cf9 \strokec9 else\cf0 \cb1 \strokec4 \
\cb3                 \cf9 \strokec9 return\cf0 \strokec4  \cf2 \strokec2 false\cf0 \strokec4 ;\cb1 \
\cb3         \}\cb1 \
\cb3         \cf9 \strokec9 return\cf0 \strokec4  \cf2 \strokec2 true\cf0 \strokec4 ;\cb1 \
\cb3     \}\cb1 \
\
\cb3     \cf5 \strokec5 std\cf0 \strokec4 ::\cf5 \strokec5 string\cf0 \strokec4  \cf6 \strokec6 cutter\cf0 \strokec4 (\cf2 \strokec2 const\cf0 \strokec4  \cf5 \strokec5 string\cf2 \strokec2 &\cf0 \strokec4  \cf7 \strokec7 s\cf0 \strokec4 )\cb1 \
\cb3     \{\cb1 \
\cb3         \cf9 \strokec9 if\cf0 \strokec4  (\cf7 \strokec7 s\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 () <= \cf8 \strokec8 0\cf0 \strokec4 )\cb1 \
\cb3             \cf9 \strokec9 return\cf0 \strokec4  \cf10 \strokec10 ""\cf0 \strokec4 ;\cb1 \
\cb3         \cf5 \strokec5 std\cf0 \strokec4 ::string res = \cf7 \strokec7 stringMap\cf0 \strokec4 [s];\cb1 \
\cb3         \cf9 \strokec9 if\cf0 \strokec4  (\cf7 \strokec7 res\cf0 \strokec4 .\cf6 \strokec6 empty\cf0 \strokec4 ())\cb1 \
\cb3         \{\cb1 \
\cb3             \cf9 \strokec9 if\cf0 \strokec4  (\cf6 \strokec6 IsPalindrome\cf0 \strokec4 (s))\cb1 \
\cb3             \{\cb1 \
\cb3                 \cf7 \strokec7 stringMap\cf0 \strokec4 [s] = s;\cb1 \
\cb3                 \cf9 \strokec9 return\cf0 \strokec4  s;\cb1 \
\cb3             \}\cb1 \
\cb3             \cf9 \strokec9 else\cf0 \cb1 \strokec4 \
\cb3             \{\cb1 \
\cb3                 \cf5 \strokec5 std\cf0 \strokec4 ::string Pal1 = \cf6 \strokec6 cutter\cf0 \strokec4 (\cf7 \strokec7 s\cf0 \strokec4 .\cf6 \strokec6 substr\cf0 \strokec4 (\cf8 \strokec8 0\cf0 \strokec4 , \cf7 \strokec7 s\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 ()-\cf8 \strokec8 1\cf0 \strokec4 ));\cb1 \
\cb3                 \cf5 \strokec5 std\cf0 \strokec4 ::string Pal2 = \cf6 \strokec6 cutter\cf0 \strokec4 (\cf7 \strokec7 s\cf0 \strokec4 .\cf6 \strokec6 substr\cf0 \strokec4 (\cf8 \strokec8 1\cf0 \strokec4 , \cf7 \strokec7 s\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 ()-\cf8 \strokec8 1\cf0 \strokec4 ));\cb1 \
\cb3                 \cf5 \strokec5 std\cf0 \strokec4 ::string res1 = (\cf7 \strokec7 Pal1\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 () >= \cf7 \strokec7 Pal2\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 ()) ? Pal1 : Pal2;\cb1 \
\cb3                 \cf7 \strokec7 stringMap\cf0 \strokec4 [s] = res1;\cb1 \
\cb3                 \cf9 \strokec9 return\cf0 \strokec4  res1;\cb1 \
\cb3             \}\cb1 \
\cb3         \}\cb1 \
\cb3         \cf9 \strokec9 else\cf0 \cb1 \strokec4 \
\cb3             \cf9 \strokec9 return\cf0 \strokec4  res;\cb1 \
\cb3     \}\cb1 \
\
\cb3     \cf5 \strokec5 string\cf0 \strokec4  \cf6 \strokec6 longestPalindrome\cf0 \strokec4 (\cf5 \strokec5 string\cf0 \strokec4  \cf7 \strokec7 s\cf0 \strokec4 ) \{\cb1 \
\cb3         \cf5 \strokec5 std\cf0 \strokec4 ::string longestPalindrome = \cf10 \strokec10 ""\cf0 \strokec4 ;\cb1 \
\cb3         \cf2 \strokec2 int\cf0 \strokec4  l = \cf8 \strokec8 0\cf0 \strokec4 ;\cb1 \
\cb3         \cf2 \strokec2 int\cf0 \strokec4  r = \cf7 \strokec7 s\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 ();\cb1 \
\cb3         \cf9 \strokec9 for\cf0 \strokec4  (\cf2 \strokec2 int\cf0 \strokec4  i = \cf8 \strokec8 0\cf0 \strokec4 ; i < r; i++)\cb1 \
\cb3         \{\cb1 \
\cb3             \cf5 \strokec5 std\cf0 \strokec4 ::string pal1= \cf6 \strokec6 cutter\cf0 \strokec4 (\cf7 \strokec7 s\cf0 \strokec4 .\cf6 \strokec6 substr\cf0 \strokec4 (l, i)); \cb1 \
\cb3             \cf5 \strokec5 std\cf0 \strokec4 ::string pal2 = \cf6 \strokec6 cutter\cf0 \strokec4 (\cf7 \strokec7 s\cf0 \strokec4 .\cf6 \strokec6 substr\cf0 \strokec4 (i, r-i));\cb1 \
\cb3             \cf9 \strokec9 if\cf0 \strokec4  (\cf7 \strokec7 pal1\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 () >= \cf7 \strokec7 pal2\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 ())\cb1 \
\cb3             \{\cb1 \
\cb3                 \cf9 \strokec9 if\cf0 \strokec4  (\cf7 \strokec7 longestPalindrome\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 () < \cf7 \strokec7 pal1\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 ())\cb1 \
\cb3                     longestPalindrome = pal1;\cb1 \
\cb3             \}\cb1 \
\cb3             \cf9 \strokec9 else\cf0 \cb1 \strokec4 \
\cb3             \{\cb1 \
\cb3                 \cf9 \strokec9 if\cf0 \strokec4  (\cf7 \strokec7 longestPalindrome\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 () < \cf7 \strokec7 pal2\cf0 \strokec4 .\cf6 \strokec6 size\cf0 \strokec4 ())\cb1 \
\cb3                     longestPalindrome = pal2;\cb1 \
\cb3             \}\cb1 \
\
\cb3         \}\cb1 \
\cb3         \cf9 \strokec9 return\cf0 \strokec4  longestPalindrome;\cb1 \
\cb3     \}\cb1 \
\cb3 \};\cb1 \
}