面试的一个问题是：给定一个三元字符串，找出只包含给定三元字符串的一个或两个字符的连续子字符串的数量。三进制字符串是最多由 3 个字符组成的字符串。例如：bcabb 是集合 {a,b,c} 上的三元字符串。上述示例的答案是：b,c,a,b,b,bc,ca,ab,bb 即.,9。
注意：子字符串由开始和结束索引决定，而不是唯一性。
谁能告诉我在这个问题中要遵循什么算法。
问问题
2470 次
6 回答
1
我无法完全理解您在说什么，但是从示例和描述中我认为答案将是2 * strlen (string) - 1。这是因为您有strlen (string)多个单长度字符串，以及strlen (string)来自给定字符串的 2 个长度子字符串。
于 2012-10-03T13:58:27.640 回答
1
这个问题需要一个后缀树。构建树后，您将按级别顺序遍历它。以下代码可以解决问题。它在 Java 中：
包 org.algocode；
导入 java.util.ArrayDeque；导入 java.util.Queue；
公共类 TernaryStringCombinator {
private static final int MAX_SIZE = 10000;
public static void main(String[] args) throws Exception {
// Read the input string.
String str = "abac";
if (str == null || str.length() > MAX_SIZE)
throw new Exception(
"Error! Input string is either null or greater than maximum allowed "
+ MAX_SIZE);
// Create the suffix tree
SuffixTree st = new SuffixTree(str);
st.levelOrderTraverse();
// You deduct one here because you don't want to count the root
// placeholder node.
System.out.println("Total nodes in tree " + (st.size() - 1));
// You deduct one here because you don't want to count the original
// string.
System.out.println("Total substrings with only one or two chars "
+ st.size2char());
}
/*
* A suffix tree is a tree of all possible contagious substrings of a
* string. It is a kind of a Trie. For example, for a given input string,
* ABBCD, the tree will store: ABBCD BBCD BCD CD D
*/
private static class SuffixTree {
private Node root;
private String s;
private int size;
private int size2char;
SuffixTree(String s_) throws Exception {
s = s_.toLowerCase();
size2char = s.length();
for (int i = 0; i < s.length(); i++)
insert(s.substring(i));
}
private void insert(String value) throws Exception {
if (root == null) {
root = new Node();
size++;
}
insert(root, value, 0);
}
// This is a recurrsive call to do the insertion
private void insert(Node node, String value, int index)
throws Exception {
Node next = null;
switch (value.charAt(index)) {
case 'a':
if (node.getA() == null)
createChildLink(node, value.charAt(index));
next = node.getA();
break;
case 'b':
if (node.getB() == null)
createChildLink(node, value.charAt(index));
next = node.getB();
break;
case 'c':
if (node.getC() == null)
createChildLink(node, value.charAt(index));
next = node.getC();
break;
default:
throw new Exception("Error! Character is not permitted. "
+ value);
}
if (index < (value.length() - 1)) {
insert(next, value.substring(index + 1), 0);
}
}
void levelOrderTraverse() {
if (root == null || root.isLeaf())
return;
Queue<Node> q = new ArrayDeque<Node>();
if (root.getA() != null)
q.add(root.getA());
if (root.getB() != null)
q.add(root.getB());
if (root.getC() != null)
q.add(root.getC());
while (!q.isEmpty()) {
Node n = (Node) q.poll();
// Only show if path has a color of 0 (two characters). Also the original
// string is not counted as a substring.
if (n.color() == 0) {
if (n.myPath().length() > 1 && !n.myPath().equalsIgnoreCase(s)) {
System.out.println("Two or more char path = "
+ n.myPath());
size2char++;
}
}
if (n.getA() != null)
q.add(n.getA());
if (n.getB() != null)
q.add(n.getB());
if (n.getC() != null)
q.add(n.getC());
}
}
Node root() {
return root;
}
int size() {
return size;
}
int size2char() {
return size2char;
}
private void createChildLink(Node parent, char childVal)
throws Exception {
Node child = new Node(parent, childVal);
size++;
switch (childVal) {
case 'a':
parent.setA(child);
break;
case 'b':
parent.setB(child);
break;
case 'c':
parent.setC(child);
break;
default:
throw new Exception("Error! Character is not permitted. "
+ childVal);
}
}
}
/*
* We will define an inner class to store a suffix tree node. Since it is a
* ternary string, we will have three child nodes of each string.
*/
private static class Node {
private Node parent;
private Node aLink;
private Node bLink;
private Node cLink;
private char value;
private String path;
// Color of a path. 0 if only one or two chars. 1 if all three are
// present in path.
private int color = 0;
Node(Node parent_, char value_) {
value = value_;
parent = parent_;
// Eagerly insert path
path = getPath();
// Eagerly calculate color. If my parent has a 1, then I will
// also be 1. If my parent has 0, then addition of myself can create
// my color to 0. This means that if my parent's path already has
// three
// characters, then I would be on a three character path.
if (parent.color() == 1)
color = 1;
else
colormyself();
}
Node() {
};
void setA(Node aLink_) {
this.aLink = aLink_;
}
void setB(Node bLink_) {
this.bLink = bLink_;
}
void setC(Node cLink_) {
this.cLink = cLink_;
}
Node getParent() {
return parent;
}
Node getA() {
return aLink;
}
Node getB() {
return bLink;
}
Node getC() {
return cLink;
}
char getValue() {
return value;
}
int color() {
return color;
}
// A special method to return combined string of parent
private String getPath() {
if (parent == null)
return null;
String path = parent.myPath();
if (path == null)
return String.valueOf(value);
StringBuilder stb = new StringBuilder();
stb.append(path);
stb.append(value);
return stb.toString();
}
String myPath() {
return path;
}
boolean isLeaf() {
return aLink == null && bLink == null && cLink == null;
}
private void colormyself() {
boolean sawA = false;
boolean sawB = false;
boolean sawC = false;
for (char c : path.toCharArray()) {
switch (c) {
case 'a':
sawA = true;
break;
case 'b':
sawB = true;
break;
case 'c':
sawC = true;
break;
}
if (sawA && sawB && sawC) {
color = 1;
break;
}
}
}
}
}
于 2012-11-02T09:59:14.107 回答
0
假设你的字符串的长度是n
所以结果将是：2*n-1
于 2012-10-03T13:58:12.667 回答
0
static void ternaryStringSubstring(String A){
System.out.println("input ternary string :"+A);
int output = 0;
for(int i=0;i<A.length();i++){
String newStr = "";
for(int j=i+1;j<=A.length();j++){
newStr = A.substring(i, j);
boolean isTernary = true;// Keep track of long loop
List<String> l = new ArrayList<String>();
for(int k=0;k<newStr.length();k++){
String sew = newStr.substring(k, k+1);
if(!l.contains(sew)){
l.add(sew);
}
if(l.size()>2){
isTernary = false;//In case its a long string, it would break
break;
}
}
if(isTernary){
output = output+1;
}
}
}
System.out.println("output :"+output);
}
让我知道更优化的解决方案
于 2012-10-16T06:22:19.373 回答
0
遍历输入字符串，逐个考虑字符。在每次迭代中，有 10 个计数器来计算不同类型的子字符串。假设您正在考虑一个职位p；那么不同类型的子串是：
- 那些在 position 之前结束的
p；我叫它result，因为当算法停止时，它会包含答案 - 那些在 position
p或之后结束，并且只包含 'a' 字符的那些；叫aa - 那些以 position
p或更晚结尾，并且只包含 'a' 和 'b' 字符的那些；叫ab - 与上述类似；叫
ac - 与上述类似；叫
ba - 与上述类似；叫
bb - 与上述类似；叫
bc - 与上述类似；叫
ca - 与上述类似；叫
cb - 与上述类似；叫
cc
p将每个计数器从位置更新为很容易p+1，例如，如果位置处的字符p是 'a'，则：
- 将所有计数器添加到
result, 以说明以结尾的所有子字符串p - 有可能继续从 'aaaaa' 到 'aaaaaa'，所以增加计数器
aa - 可以将“a”附加到“ba”类型的任何子字符串
- 可以将“a”附加到“ab”类型的任何子字符串，使其成为“ba”，因此将计数器添加
ab到ba - 可以将“a”附加到“b”类型的任何子字符串，使其成为“ba”，因此将计数器添加
b到ba - 无法将“a”附加到任何其他子字符串，因此将所有其他计数器设置为零
代码片段：
...
int result = 0;
int counters[3][3] = {{0}}; // [0][0] is aa; [0][1] is ab, etc
int L, x, y; // L represents the current Letter; x and y represent other letters
int p; // position in input string
for (p = 0; ; p++)
{
for (y = 0; y < 3; y++)
for (x = 0; x < 3; x++)
result += counters[y][x];
switch (str[p])
{
case 'a': L = 0; x = 1; y = 2; break;
case 'b': L = 1; x = 2; y = 0; break;
case 'c': L = 2; x = 0; y = 1; break;
case '\0': return result;
default: abort();
}
counters[L][L] += 1;
counters[x][L] += counters[x][x] + counters[L][x];
counters[y][L] += counters[y][y] + counters[L][y];
counters[L][x] = 0;
counters[x][x] = 0;
counters[y][x] = 0;
counters[L][y] = 0;
counters[x][y] = 0;
counters[y][y] = 0;
}
奇怪的是，此代码为 string 输出 10（而不是 9），为 string 输出bcabb18（而不是 17）abbaccb。我把它作为一个有趣的练习让你发现缺少哪个子字符串......
于 2012-10-03T19:17:15.490 回答
0
首先，我可以看到您正在打印重复的元素。我假设字符串的大小是'n'。因此，无论它们是否重复，您都必须打印 n 个元素。两个连续元素的相同保持，因此取'n-1'。到目前为止的总数是'2n-1'。现在搜索 2 个连续元素并为其添加“+2”（前提是前面和后面的字符不为空）。现在搜索 3 个连续元素并总共添加“+3”。重复此操作直到“n”，因为可能有“n”个重复字符。全部添加。希望这可以帮助。
于 2013-07-11T19:22:47.123 回答