leetCode- 472. Concatenated Words

leetCode-   472. Concatenated Words

因为每个组合的字符串,至少要有3个index。 起点,中间拼接点,结点。所以可以将字符串分解为子字符串,判断子字符串是否存在。但是,后面字符串的存在必须要在前面字符串已经存在基础上判断。

leetCode-   472. Concatenated Words

class Solution {
public: vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
//使用set容器将所有字符串存起了,因为set有count函数可以查找元素是否存在
set<string> s(words.begin(),words.end());
vector<string> res; for(int i=;i<s.size();i++)
{
string w=words[i];
int n=w.size();
//定义一个数组存标记是否当前位置之前的字符串能找到
int * dp=new int[n+]();
//string的第一个位置之前为空,因此置为1
dp[]=;
for(int j=;j<n;j++)
{
//在当前位置之前的substring都能找到的情况下,才需要考虑后面的string
if(dp[j]==) continue;
for(int k=j+;k<=n;k++)
{
//如果从当前位置到某个位置的字符串能找到,将标记置为1
//k-j<n 不能少,少了可能将字符串自己看为自己的子字符串。
// substr(i,k-j), i 为起始位置,k-j为个数,最大的个数为n,因此k从i+1 到n。
if(k-j<n&&s.count(w.substr(j,k-j))) dp[k]=;
}
if(dp[n])
{
res.push_back(w);
break;
}
}
}
return res;
} };

substr (startpos, length);  startpos是起始字符的符号,length为从 startpos开始取的字符串的长度,包括startpos。

动态数组初始化:

对于内置数据类型元素的数组,必须使用() 来显式初始化,否则程序不执行初始化操作。

int * p= new int[10];//每个元素都没有初始化,p指向的int值是不确定的

int * p=new int[10]();//每个元素初始化为0

类类型初始化,如果显式定义无参的构造函数,则调用都调用无参构造函数:

class A
{
public:
int a;
A()
{
a=;
}
};

A *m =new A();
A *n = new A;
cout<<m->a<<endl;
cout<<n->a<<endl;

都输出1

类类型,如果没有显式定义无参的构造函数,则调用默认构造函数:

class A
{
public:
int a; };
int main()
{
A *m =new A();
A *n = new A;
cout<<m->a<<endl;
cout<<n->a<<endl;
}

输出

0
8132528

因为内部数据类型int 加() 才能初始化。

 

string *psa = new string[10];  // 每个元素调用默认构造函数初始化

string *psa = new string[10]();  // 每个元素调用默认构造函数初始化

输出都为空,因为string 类有无参的构造函数。

type *p=new type 不同于
type *p=new type()
前者只具有创建对象(变量)的作用,后者还具有初始化对象(变量)为0的作用!
*顺便提一句: classXX p; 和 classXX p();不一样,
前者是调用empty constructor来创建对象,并且不具备初始化为0的作用,
而后者则是声明了一个名字为p、返回类型为classXX的函数!

 

声明只是表示一个对象的引用,比如我们的语句:

MyClasee myclass;//这个是在栈上创建一个类对象 程序退出其作用域后自动调用类的析构函数.

这里是一个空引用,而通过new关键字可以实例化一个MyClasee的实例,

所以语句:

myclass = new MyClass();//这个是在堆上创建一个类对象, 必须手动delete释放对象 否则会造成内存泄露的.

他的生存期就是他所处的语句块(也就是离他最近的一对{}),离开了他的生存期他就失效了,一般声明形式就是在栈中定义的。堆上的空间需要你用new申请,用delete或者delete[]归还,在进程的范围内,该内存的生存期就完全由你操作了;

 

当显式定义了一个构造函数之后,系统设定的default empty construct(默认构造函数)不存在了。尤其是定义了有参数的构造函数之后,必须定义一个无参的构造函数,否则A a; 或者A * a=new A;或A * a=new A() 不能通过编译。

leetCode-   472. Concatenated Words

上一篇:深入理解Java虚拟机04--类结构文件


下一篇:mysql数据库去重语句和不同表之间列的复制语句