- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
子字符串是字符串中连续的字符范围。
现在我需要找出有多少个可以重新排列的子串可以形成一个回文。
例如:输入-aabb
a
aa
aab (because after re-arranging it becomes aba)
aabb (because after re-arranging it becomes abba)
a
abb (because after re-arranging it becomes bab)
b
bb
b
So we have 9 substring palindromes.
这是我试过的代码:
public static int getPalindromeCount(String str) {
// all single characters are treated as palindrome
int count = str.length();
// Get all sub strings
List<String> subs = new ArrayList<>();
subString(str, subs);
for (String sub : subs) {
String rev = new StringBuilder(sub).reverse().toString();
if (rev.equals(sub)) {
System.out.println(sub);
count++;
} else {
boolean valid = isPalindrome(sub);
System.out.println(sub + " : " + valid);
if (valid) {
count++;
}
}
}
return count;
}
// Check if substring can form a Palindrome
private static boolean isPalindrome(String input) {
Set<Character> oddChars = new HashSet<>();
for (char c : input.toCharArray()) {
if (!oddChars.add(c)) {
oddChars.remove(c);
}
}
return oddChars.size() <= 1;
}
// Get all substrings
private static void subString(String input, List<String> list) {
for (int i = 0; i < input.length(); i++) {
for (int j = i + 2; j <= input.length(); j++) {
list.add(input.substring(i, j));
}
}
}
方法 isPalindrome
我从这篇文章中获取的部分逻辑 Check if a permutation of a string can become a palindrome
此代码运行良好,但因超时错误而失败。
我不确定失败的输入是什么,因为它们隐藏在我的 hackerrank 挑战中。
编辑:
我修改了我的 getPalidromeCount
方法来检查输入中有多少个奇数字母来决定回文数。
这是基于对这篇文章的评论:
Hint: A palindrome consists of all letters of even count or all letters of even count with one letter of odd count(the middle character). Now, you could count possible palindromes easily. – vivek_23
public static int getPalindromeCount(String str) {
List<Integer> list = new ArrayList<>(strToEvaluate.size());
for (String str : strToEvaluate) {
int count = str.length();
List<String> subs = new ArrayList<>();
subString(str, subs);
for (String sub : subs) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < sub.length(); i++) {
char c = sub.charAt(i);
map.put(c, map.getOrDefault(c, 0) + 1);
}
int odds = 0;
for (char key : map.keySet()) {
if (map.get(key) % 2 != 0) {
odds++;
if (odds > 1) {
break;
}
}
}
if (odds <= 1) {
System.out.println(sub);
count++;
}
list.add(count);
}
}
return list;
}
但我仍然看到超时错误。我没有在此逻辑中使用 isPalindrome
方法。
最佳答案
有 n(n+1)/2
个可能的子串,对于每个子串,您检查它是否可以重新排列,以便在 O(k)< 中形成回文
其中 k
是给定子字符串的长度,让我们考虑是否有必要分别解析每个子字符串。
假设您有从索引 p
到 k
的子字符串,对于从索引 p
到 k + 的子字符串,您能说些什么? 1
。真的有必要单独解析这个扩展子串吗?
关于java - 从给定的字符串中获取所有可能的回文,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56989233/
降本手段一招鲜,增效方法吃遍天; 01 互联网行业里; 降本策略千奇百怪,手段却出奇一致;增效方法五花八门,手段更是花里胡哨; 对于企业来说;
有什么方法可以使用 angularjs 中的部分进行代码分组吗? 原因 --- 我的 Controller 包含太多代码。该 Controller 包含了多个方法和大量功能的代码,降低了代码的可读性。
不幸的是,我的数据库的数据模型必须改变,所以我正在寻找最轻松的方式来迁移我的数据。 此时情况如何: create table cargo{ id serial primary key, per
在 QTextEdit 对象中,假设我想知道字符在鼠标光标下的位置。 我会写... void MyQTextEditObject::mousePressEvent(QMouseEvent* mouse
是否可以在 C++ 中返回一个 return 语句或做一些具有类似功能的事情? 例如,如果代码中有几个函数将指针作为输入,并且每个函数都检查指针是否为 nullptr,这将很方便。如果它是一个 nul
我的 PC 上有一个控制台应用程序,它是 signalR 服务器。 我有一个 html 页面,它是互联网上的 signalR 客户端。但我尝试连接服务器,但我有一个错误的请求 400 错误。如果服务器
我想将应用程序作为后台进程运行。当点击应用程序图标时,它不会显示任何 View ,只会启动后台进程。 最佳答案 对于 iOS 这是不可能的,但是对于 android,react native 有 he
我知道有(昂贵的)框架可以让你在 VS C# 中编写 android 应用程序并将其编译为 android apk。 我也知道,可以在 VS 中编写 Java 应用程序(link)。 是否有可能,甚至
我在做: can :manage, :all if user.role == 'admin' can :approve, Anuncio do |anuncio| anuncio.try(:apr
我是一名优秀的程序员,十分优秀!