Problem:
Given a string, return the longest substring that appears at both the beginning and end of the string without overlapping. For example, sameEnds("abXab") is "ab".
sameEnds("abXYab") → "ab"
sameEnds("xx") → "x"
sameEnds("xxx") → "x"
Solution:
public String sameEnds(String string) {
int len = string.length();
String fin = "";
String tmp = "";
for (int i = 0; i < len; i++) {
tmp += string.charAt(i);
int tmplen = tmp.length();
if (i < len / 2 && tmp.equals(string.substring(len-tmplen,len)))
fin = tmp;
}
return fin;
}
Alternate solution:
ReplyDeletepublic String sameEnds(String string) {
String result="";
for(int i=0;i<string.length()/2+1;i++){
if(string.substring(0,i).equals(string.substring(string.length()-i)))
result=string.substring(0,i);
}
return result;
}
I like it!
DeleteYet another alternative:
ReplyDeletepublic String sameEnds(String string) {
if (string == null) {
return "";
}
String front = "";
String end = "";
for (int i = string.length()/2; i >= 0; i--) {
front = string.substring(0, i);
end = string.substring(string.length() - i);
if (front.equals(end)) break;
}
return front;
}
I always use helper methods, no matter what.
ReplyDeletepublic String sameEnds(String str) {
int max = 0;
for(int i = 0; i <= str.length() / 2; i++){
if(str.substring(0,i).equals(fromEndPoint(str, i)) && i > max){
max = i;
}
}
return str.substring(0,max);
}
public String fromEndPoint(String str, int a){
return str.substring(str.length() - a);
}
Helper methods are great for recursive functions, though having a "helper method, no matter what" is not always the best idea. You increase more unnecessary code, which also increases more calls to the stack and adds to the algorithmic complexity and more headache for anyone who will ever have to maintain your "helper method, no matter what" attitude, get me drift sir, cause I should write a helper function to help this function help while it helps your method while you help.
Deletepublic String sameEnds(String str) {
ReplyDeleteint odd_adder = 0;
if( str.length() % 2 == 1 ) odd_adder = 1;
for(int x = 0; x < str.length()/2; x++){
if((str.substring(0,str.length() /2 - x)).equals(str.substring(odd_adder+x+str.length()/2)))
return (str.substring(0,str.length()/2 - x));
}
return "";
}
While your solution works, it doesn't make very good use of memory when you consider the fact that strings in java are immutable. Every single iteration of the loop creates a new array in memory. In addition, the substring method has an O(m) complexity where m is the size of the substring. Also the .equals() method is another O(n) operation which becomes very expensive when the size of the string becomes very big. An extremely stupid and convoluted solution which seeks to avail these two concerns is below.
ReplyDeletepublic String sameEnds(String string) {
StringBuilder st = new StringBuilder();
int j = string.length()-1;
boolean start = false;
for(int i = string.length()/2-1; i>=0 ; i--){
if(start){
if(string.charAt(i)==string.charAt(j)){
st.append(string.charAt(i));
j--;
}else{
st=new StringBuilder();
start=false;
}
}else{
if(string.charAt(i)==string.charAt(j)){
start=true;
j--;
st.append(string.charAt(i));
}
}
}
return st.reverse().toString();
}
public String sameEnds(String string) {
ReplyDeleteString result = "";
for (int i=0; i<string.length()/2; i++){
if (string.substring(0, i+1).equals(string.substring(string.length()-i-1))){
result = string.substring(0, i+1);
}//else break;
}
return result;
}
public String sameEnds(String string) {
ReplyDeleteString firstHalf = string.substring(0,string.length()/2);
String secondHalf = string.substring(string.length()/2);
if(firstHalf.length()<secondHalf.length()){
secondHalf = secondHalf.substring(1);
}
int len = firstHalf.length();
for(int i=0; i<len;i++){
if(firstHalf.equals(secondHalf)){
return firstHalf;
}
firstHalf = firstHalf.substring(0,firstHalf.length()-1);
secondHalf = secondHalf.substring(1);
}
return "";
}
String same = "";
ReplyDeleteint i = 0;
while(i<=string.length()/2)
{
String start = string.substring(0,i);
String end = string.substring(string.length()-i);
if(start.equals(end))same = start;
i++;
}
return same;
public String sameEnds(String string) {
ReplyDeleteif (string.length() == 0)
{
return "";
}
int start = string.substring(string.length() / 2).indexOf(string.charAt(0));
if (start >= 0)
{
String ends = string.substring(0, 1);
int pos = 1;
if (start == 0 && string.length() % 2 != 0)
{
ends = "";
pos= 0;
}
start += + string.length() / 2;
for (int i = start + 1; i < string.length(); i++)
{
if (string.charAt(i) == string.charAt(pos))
{
ends += string.charAt(i);
pos++;
}
else
{
return ends;
}
}
return ends;
}
else
{
return "";
}
}
u dont need to use 2 parameter man just use substring(len-word) .
ReplyDeletepublic String sameEnds(String string) {
ReplyDeleteString sub = "";
for (int i = 0; i <= string.length() / 2; i++)
{
if (string.substring(0, i).equals(string.substring(string.length() - i, string.length())))
{
sub = string.substring(0, i);
}
}
return sub;
}
why is that we iterate for loop with string.length()/2
ReplyDeletefor prevent overlapping. for example;
Delete("abababababab")("ab") gives ("abababababab")
what fonction should return is
("ababab")
public String sameEnds(String string) {
ReplyDeleteint len = string.length();
String res = "";
for (int i = 1; i <= string.length() / 2; i++) {
String tmp = string.substring(0, i);
if (tmp.equals(string.substring(len - tmp.length()))) {
res = tmp;
}
}
return res;
}
public String sameEnds(String string) {
ReplyDeleteString res = "";
int sLen = string.length();
for (int i = 1, j = sLen - 1; i <= sLen / 2; i++, j--) {
if (string.substring(0, i).equals(string.substring(j))) {
res = string.substring(0, i);
}
}
return res;
}