# C++, generate palindrome by DFS, then verify

• The idea is to generate possible palindrome number from great to small, which is 2n or 2n-1 digit. Check whether it is product of 2 n-digit number. If so, return the answer. For n = 2-10, it seems that there is always a number of 2n digit matching the requirements.
I feel the solution to this question is like brute force, but with a bit optimization.

``````class Solution {
public:
int largestPalindrome(int n) {
string s(n*2,'0');
// for case: abccba
int ans = helper(s, 0, 2*n-1);
if (ans != -1) return ans;
s.pop_back();
// for case: abcba; This is unnecessary for n: 2-10
return helper(s, 0, 2*n-2);
}
private:
// build palindrome number from great to small by backtracking
// check whether it is product of 2 n-digit numbers
int helper(string& s, int l, int r) {
if (l > r) return check(s);
for (int i = 9; i >= 0; i--) {
if (l == 0 && i == 0) continue;
s[l] = '0'+i;
s[r] = '0'+i;
int ans = helper(s, l+1, r-1);
if (ans != -1) return ans;
}
return -1;
}
int check(string& s) {
int n = (s.size()+1)/2;
long m = 0;
for (int i = 0; i < s.size(); i++)
m = m*10+s[i]-'0';
// if exsiting, the smaller numbers is in range [left, right]
long left = pow(10, n-1), right = sqrt(m);
for (long i = right; i >= left && m/i < left*10; i--) {
if (i*(m/i) == m) return m%1337;
}
return -1;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.